Pagini recente » Cod sursa (job #2887586) | Cod sursa (job #828537) | Cod sursa (job #979756) | Cod sursa (job #841165) | Cod sursa (job #1320092)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
int n,poz;
double ARC,mx,D;
bool v[120050];
struct punct{
double x,y;
};
punct c[120050],p[120050],mn;
int cmp(punct XX,punct YY)
{
if(XX.x==YY.x)
return XX.y<YY.y;
return XX.x<YY.x;
}
double det(int A,int B,int C)
{
return 1;
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;
for(i=1;i<=n;i++)
fscanf(f,"%lf%lf",&p[i].x,&p[i].y),mn.y=min(mn.y,p[i].y);
sort(p+1,p+n+1,cmp);
mn.x=p[1].x;
for(i=n;i>=1;i--)
p[i].x-=mn.x,p[i].y-=mn.y;
c[1].x=p[1].x;c[1].y=p[1].y;
c[2].x=p[2].x;c[2].y=p[2].y;
v[1]=true;v[2]=true;
int sf=2;
for(i=3;i<n;i++)
{
j=1;
while(v[j])
j++;
mx=atan2(c[sf].x-p[j].x,c[sf].y-p[j].y);
poz=j;
for(j=1;j<=n;j++)
{
if(!v[j])
{
ARC=atan2(c[sf].x-p[j].x,c[sf].y-p[j].y);
if(ARC<mx)
mx=ARC,poz=j;
}
}
v[poz]=true;
sf++;
c[sf].x=p[poz].x;
c[sf].y=p[poz].y;
D=det(sf-2,sf,sf-1);
while(D<0)
{
sf--;
D=det(sf-2,sf,sf-1);
}
}
D=det(1,sf,sf-1);
while(D<0)
{
sf--;
D=det(1,sf,sf-1);
}
fprintf(g,"%d\n",sf);
for(i=sf;i>=1;i--)
{
fprintf(g,"%.6f %.6f\n",c[i].x+mn.x,c[i].y+mn.y);
}
return 0;
}