Pagini recente » Cod sursa (job #1405069) | Cod sursa (job #3293530) | Cod sursa (job #1168343) | Cod sursa (job #2340446) | Cod sursa (job #1129784)
#include<fstream>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N,k;
struct point { double x,y;} P[120090],st[120009];
double crossproduct(point A,point B,point C)
{
return static_cast<double>(A.x*B.y+A.y*C.x+B.x*C.y-B.y*C.x-A.y*B.x-A.x*C.y);
}
bool cmp(point A,point B)
{
return crossproduct(P[1],A,B)>0;
}
int main()
{
f>>N;
f>>P[1].x>>P[1].y;
for(int i=2;i<=N;++i)
{
f>>P[i].x>>P[i].y;
if(P[1].x>P[i].x || (P[1].x==P[i].x && P[1].y>P[i].y))
swap(P[1],P[i]);
}
sort(P+2,P+1+N,cmp);
st[1]=P[1], st[2]=P[2];
k=2;
for(int i=3;i<=N;++i)
{
while(crossproduct(st[k-1],st[k],P[i])<0 && k>=2)--k;
st[++k]=P[i];
}
g<<k<<'\n';
g.precision(12);
for(int i=1;i<=k;++i)
g<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
f.close();g.close();
return 0;
}