Pagini recente » Cod sursa (job #2906877) | Cod sursa (job #2922801) | Cod sursa (job #822135) | Cod sursa (job #539419) | Cod sursa (job #1928336)
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 120005
#define PI 3.141592
using namespace std;
FILE*IN,*OUT;
int N,Lower[MaxN],Upper[MaxN],UpSize=1,LowSize=1;
struct Point
{
double x,y;
}v[MaxN];
bool cond(Point a,Point b)
{
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double Angle(int x,int y)
{
return atan2(v[x].y-v[y].y,v[x].x-v[y].x);
}
int main()
{
IN=fopen("infasuratoare.in","r");
OUT=fopen("infasuratoare.out","w");
fscanf(IN,"%d",&N);
for(int i=1;i<=N;i++)
fscanf(IN,"%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+1+N,cond);
Lower[1]=Upper[1]=1;
for(int i=2;i<=N;i++)
{
while(UpSize>1&&Angle(i,Upper[UpSize-1])-Angle(Upper[UpSize],Upper[UpSize-1])>0)
UpSize--;
Upper[++UpSize]=i;
while(LowSize>1&&Angle(i,Lower[LowSize-1])-Angle(Lower[LowSize],Lower[LowSize-1])<0)
LowSize--;
Lower[++LowSize]=i;
}
fprintf(OUT,"%d\n",UpSize+LowSize-2);
for(int i=1;i<=LowSize;i++)
fprintf(OUT,"%lf %lf\n",v[Lower[i]].x,v[Lower[i]].y);
for(int i=UpSize-1;i>1;i--)
fprintf(OUT,"%lf %lf\n",v[Upper[i]].x,v[Upper[i]].y);
return 0;
}