Pagini recente » Cod sursa (job #1083182) | Cod sursa (job #2264880) | Cod sursa (job #28980) | Cod sursa (job #2140703) | Cod sursa (job #1738436)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
int N;
typedef struct {double x,y;} POINT;
POINT V[120005],p0;
POINT puncte[120005];
int i,poz;
POINT st[120005];
int orient(POINT A,POINT B,POINT C)
{
int val=(B.y-A.y)*(C.x-B.x)-(C.y-B.y)*(B.x-A.x);
if(val<0)
return -1;
if(val>0)
return 1;
return 0;
}
int dist(POINT a,POINT b)
{
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
bool comp(POINT a,POINT b)
{
int val=orient(p0,a,b);
if(val==0)
{
if(dist(a,p0)>=dist(b,p0))
return 0;
return 1;
}
if(val==-1)
return 1;
return 0;
}
int main()
{
fscanf(f,"%d",&N);
poz=1;
for(i=1;i<=N;i++)
{
fscanf(f,"%lf %lf",&V[i].x,&V[i].y);
if(V[i].y<V[poz].y||(V[i].y==V[poz].y&&V[i].x<V[poz].x))
poz=i;
}
swap(V[1],V[poz]);
p0=V[1];
sort(V+2,V+1+N,comp);
puncte[(int)(++puncte[0].x)]=V[1];
for(i=2;i<=N;i++)
{
while(i<N&&orient(p0,V[i],V[i+1])==0)
i++;
puncte[(int)(++puncte[0].x)]=V[i];
}
st[(int)(++st[0].x)]=puncte[1];
st[(int)(++st[0].x)]=puncte[2];
for(i=3;i<=puncte[0].x;i++)
{
while(orient(st[(int)(st[0].x-1)],st[(int)(st[0].x)],puncte[i])>=0)
{
st[0].x--;
}
st[(int)(++st[0].x)]=puncte[i];
}
fprintf(g,"%d\n",(int)st[0].x);
for(i=1;i<=st[0].x;i++)
{
fprintf(g,"%f %f\n",st[i].x,st[i].y);
}
fclose(f);
fclose(g);
return 0;
}