Pagini recente » Cod sursa (job #2094707) | Cod sursa (job #1885764) | Cod sursa (job #1328905) | Cod sursa (job #2574996) | Cod sursa (job #3354666)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct q
{
double x, y;
};
q v[120005];
int cmp(q a, q b)
{
if(a.x<b.x)
{
return true;
}
else if(a.x>b.x)
{
return false;
}
else
{
if(a.y<b.y)
{
return true;
}
return false;
}
}
int arie(q a, q b, q c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
q st1[120005], st2[120005];
int main()
{
int n;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v+1, v+n+1, cmp);
int k1=2;
st1[1].x=v[1].x;
st1[1].y=v[1].y;
st1[2].y=v[2].y;
st1[2].x=v[2].x;
for(int i=3;i<=n;i++)
{
while(k1>2 && arie(st1[k1-1], st1[k1], v[i])<0)
{
k1--;
}
st1[++k1]=v[i];
}
int ktotal=0;
ktotal+=k1;
int k2=2;
st2[1].x=v[1].x;
st2[1].y=v[1].y;
st2[2].y=v[2].y;
st2[2].x=v[2].x;
for(int i=3;i<=n;i++)
{
while(k2>2 && arie(st2[k2-1], st2[k2], v[i])>0)
{
k2--;
}
st2[++k2]=v[i];
}
ktotal+=k2;
fout<<ktotal-3<<"\n";
for(int i=1;i<=k1;i++)
{
fout<<st1[i].x<<" "<<st1[i].y<<"\n";
}
for(int i=k2-2;i>0;i--)
{
fout<<st2[i].x<<" "<<st2[i].y<<"\n";
}
return 0;
}