Pagini recente » Cod sursa (job #3121207) | Cod sursa (job #2034415) | Cod sursa (job #775502) | Cod sursa (job #499519) | Cod sursa (job #1917927)
#include <iostream>
#include<fstream>
#include<iomanip>
#include<algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,st[240010],sz,viz[120011],q;
struct coord
{
double x,y;
};
coord C[120011];
double det(int i,int j,int k)
{
double x=C[i].x;
double y=C[i].y;
double x2=C[j].x;
double y2=C[j].y;
double x3=C[k].x;
double y3=C[k].y;
return (x*y2+x2*y3+x3*y-x3*y2-x2*y-x*y3);
}
bool comp(coord a,coord b)
{
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
f>>C[i].x>>C[i].y;
sort(C+1,C+n+1,comp);
st[++sz]=1;
st[++sz]=2;
viz[2]=1;
i=3;
q=1;
while(!viz[1])
{
while(viz[i])
{
if(i==n)
q=-1;
i+=q;
}
while(sz>=2 && det(st[sz-1],st[sz],i)<0)
{
viz[st[sz]]=0;
sz--;
}
st[++sz]=i;
viz[i]=1;
}
g<<sz-1<<'\n';
for(i=1;i<sz;i++)
g<<setprecision(7)<<fixed<<C[st[i]].x<<' '<<C[st[i]].y<<'\n';
}