Pagini recente » Cod sursa (job #761469) | Cod sursa (job #1016798) | Cod sursa (job #1424083) | Cod sursa (job #1899255) | Cod sursa (job #923725)
Cod sursa(job #923725)
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#define eps 1.e-12
using namespace std;
struct POINT
{
double x,y;
};
POINT ll,t;
int n,i,top,st[120100],poz;
double a1,a2;
vector <POINT> v;
double ccw(POINT p1,POINT p2,POINT p3)
{
return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
bool cmp(const POINT &a,const POINT &b)
{
if(fabs(a.x-ll.x)<eps&&fabs(a.y-ll.y)<eps)
return 1;
if(fabs(b.x-ll.x)<eps&&fabs(b.y-ll.y)<eps)
return 0;
if(ccw(ll,a,b)>eps)
return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
ll.x=1000000001;
ll.y=1000000001;
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&a1,&a2);
t.x=a1;
t.y=a2;
if(t.y-ll.y<-eps)
{
ll.x=t.x;
ll.y=t.y;
}
if(fabs(t.y-ll.y)<eps)
{
if(t.x-ll.x<-eps)
{
ll.x=t.x;
ll.y=t.y;
}
}
v.push_back(t);
}
sort(v.begin(),v.end(),cmp);
v.push_back(ll);
st[0]=0;
st[1]=1;
top=1;
i=2;
while(i<=n)
{
if(ccw(v[st[top-1]],v[st[top]],v[i])>eps)
{
st[++top]=i;
i++;
}
else
top--;
}
printf("%d\n",top);
for(i=0;i<top;i++)
printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}