Pagini recente » Cod sursa (job #2214196) | Cod sursa (job #3121343) | Cod sursa (job #449840) | Cod sursa (job #984842) | Cod sursa (job #1320132)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
int n,poz;
double ARC,mx,D;
struct puncte{
double x,y,arc;
};
puncte aux,p[120050];
struct punct{
double x,y;
};
punct c[120050],mn;
int cmp(puncte XX,puncte YY)
{
if(XX.arc==YY.arc)
{
if(XX.x==0)
{
return XX.y>YY.y;
}
else if(XX.x==YY.x)
return XX.y<YY.y;
return XX.x<YY.x;
}
return XX.arc<YY.arc;
}
double det(int A,int B,int C)
{
return c[A].x*c[B].y+c[B].x*c[C].y+c[C].x*c[A].y-c[A].y*c[B].x-c[B].y*c[C].x-c[C].y*c[A].x;
}
int main()
{
int i,j;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
fscanf(f,"%d",&n);
mn.y=1000000000;
mn.x=1000000000;
for(i=1;i<=n;i++)
{
fscanf(f,"%lf%lf",&p[i].x,&p[i].y);
if(mn.x>p[i].x)
{
mn.x=p[i].x;
mn.y=p[i].y;
}
else if(mn.x==p[i].x)
if(p[i].y<mn.y)
mn.y=p[i].y;
}
for(i=n;i>=1;i--)
{
p[i].x-=mn.x;
p[i].y-=mn.y;
if(p[i].x==0 && p[i].y==0) j=i;
}
p[j].x=p[1].x;
p[j].y=p[1].y;
p[1].x=0;
p[1].y=0;
for(i=1;i<=n;i++)
p[i].arc=atan2(p[i].x,p[i].y);
sort(p+1,p+n+1,cmp);
c[1].x=p[1].x;c[1].y=p[1].y;
c[2].x=p[2].x;c[2].y=p[2].y;
int sf=2;
for(i=3;i<=n;i++)
{
sf++;
c[sf].x=p[i].x;
c[sf].y=p[i].y;
D=det(sf-2,sf,sf-1);
while(D<0)
{
c[sf-1].x=c[sf].x;
c[sf-1].y=c[sf].y;
sf--;
D=det(sf-2,sf,sf-1);
}
}
D=det(1,sf,sf-1);
while(D<0)
{
c[sf-1].x=c[sf].x;
c[sf-1].y=c[sf].y;
sf--;
D=det(1,sf,sf-1);
}
fprintf(g,"%d\n",sf);
fprintf(g,"%.6f %.6f\n",c[1].x+mn.x,c[1].y+mn.y);
for(i=sf;i>=2;i--)
{
fprintf(g,"%.6f %.6f\n",c[i].x+mn.x,c[i].y+mn.y);
}
return 0;
}