Pagini recente » Cod sursa (job #1498421) | Cod sursa (job #2637261) | Cod sursa (job #78136) | Cod sursa (job #1525148) | Cod sursa (job #995399)
Cod sursa(job #995399)
#include<cstdio>
#include<algorithm>
#define Point pair<double,double>
#define x first
#define y second
using namespace std;
const int NMAX = 120005;
int N,i,Min,Cnt;
Point P[NMAX],St[NMAX];
inline double CrossProduct(Point A,Point B,Point C)
{
return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
}
bool cmp(Point A,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",&P[i].x);
scanf("%lf",&P[i].y);
if(P[i]<P[Min]) Min=i;
}
swap(P[Min],P[1]); sort(P+2,P+N+1,cmp);
St[1]=P[1]; St[2]=P[2]; Cnt=2;
for(i=3;i<=N;i++)
{
while(Cnt>=2 && CrossProduct(St[Cnt-1],St[Cnt],P[i])>0) Cnt--;
St[++Cnt]=P[i];
}
printf("%d\n",Cnt);
for(i=Cnt;i;i--) printf("%lf %lf\n",St[i].x,St[i].y);
return 0;
}