Mai intai trebuie sa te autentifici.
Cod sursa(job #1053350)
Utilizator | Data | 12 decembrie 2013 18:07:42 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.89 kb |
#include<cstdio>
#include<algorithm>
#define Point pair<double,double>
#define x first
#define y second
using namespace std;
int N,Min,i,Cnt,St[120005];
Point P[120005];
double CrossProduct(Point A,Point B,Point C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-A.y*B.x-B.y*C.x-C.y*A.x;
}
bool cmp(const Point &A,const Point &B)
{
return CrossProduct(P[1],A,B)<0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N); Min=1;
for(i=1;i<=N;i++)
{
scanf("%lf%lf",&P[i].x,&P[i].y);
if(P[i]<P[Min]) Min=i;
}
swap(P[Min],P[1]); sort(P+2,P+N+1,cmp);
for(i=1;i<=N;i++)
{
while(Cnt>=2 && CrossProduct(P[St[Cnt-1]],P[St[Cnt]],P[i])>0) Cnt--;
St[++Cnt]=i;
}
printf("%d\n",Cnt);
for(i=Cnt;i;i--) printf("%lf %lf\n",P[St[i]].x,P[St[i]].y);
return 0;
}