Pagini recente » Cod sursa (job #1150133) | Cod sursa (job #1805015) | Cod sursa (job #2693954) | Cod sursa (job #2412860) | Cod sursa (job #1151184)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define NM 120005
#define mxy 1000000001
#define PI 3.141592653
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
struct p{float x;float y;};
int i,N;
bool b[NM];
float c1,c2;
p A0,v[NM],st[NM];
float d(p i,p j)
{
return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y));
}
bool ung(p i,p j,p k)
{
return i.x*j.y+j.x*k.y+k.x*i.y-i.x*k.y-j.x*i.y-k.x*j.y>0;
}
bool cmp(p i,p j)
{
float c1,c2;
c1=acos((i.x-A0.x)/d(A0,i));
c2=acos((j.x-A0.x)/d(A0,j));
if(c1==c2) return d(A0,i)<d(A0,j);
return c1<c2;
}
int main()
{
fscanf(f,"%d",&N);
A0.x=A0.y=mxy; int ii;
for(i=1;i<=N;i++)
{
fscanf(f,"%f%f",&v[i].x,&v[i].y);
if(v[i].y<A0.y) {A0.x=v[i].x; A0.y=v[i].y; ii=i;}
if(v[i].y==A0.y&&v[i].x<A0.x) {A0.x=v[i].x; ii=i;}
}
v[ii].x=v[ii].y=0;
stable_sort(v+1,v+N+1,cmp);
for(i=1;i<=N;i++)
{
c1=acos((v[i].x-A0.x)/d(A0,v[i]));
c2=acos((v[i+1].x-A0.x)/d(A0,v[i+1]));
if(c1==c2) b[i]=1;
}
st[0]=A0;
i=1; while(b[i]) i++;
st[1]=v[i]; i++;
while(b[i]) i++;
st[2]=v[i]; i++;
int u(2);
for(;i<=N;i++)
if(!b[i])
{
while(ung(v[i],st[u],st[u-1])) u--;
st[++u]=v[i];
}
fprintf(g,"%d\n",u+1);
for(i=0;i<=u;i++)
fprintf(g,"%f %f\n",st[i].x,st[i].y);
return 0;
}