Pagini recente » Monitorul de evaluare | Cod sursa (job #2069849) | Monitorul de evaluare | Cod sursa (job #2573079) | Cod sursa (job #696091)
Cod sursa(job #696091)
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
#define dist (sqrt(a.x*a.x+a.y*a.y))
#define pi 3.14159265
using namespace std;
struct punct
{
float x,y;
}v[120000],aux;
int m,n,i,j,k,q[120000];
bool ok;
inline float panta(float x1, float y1, float x2, float y2)
{
if(x2-x1<0.0001) return 2000000000;
return((y2-y1)/(x2-x1));
}
inline float mm(float k)
{
return (k>0? k : -k);
}
bool cmp(punct x , punct y)
{
return (panta ( v[0].x , v[0].y , x.x , x.y ) < panta ( v[0].x , v[0].y , y.x , y.y ) );
}
inline float unghi(punct a, punct o)
{
a.x-=o.x;a.y-=o.y;
float qq;
qq=0;
if(a.x>0&&a.y>0) qq= ( asin(a.y/dist));
if(a.x<0&&a.y>0) qq= (pi/2 + asin(-a.x/dist));
if(a.x<0&&a.y<0) qq= (pi + asin(-a.y/dist));
if(a.x>0&&a.y<0) qq= (3*pi/2 + asin(a.x/dist));
if(mm(a.x)<0.001)
{
if(a.y>0) qq=pi/2;
if(a.y<0) qq=3*pi/2;
}
if(mm(a.y)<0.001)
{
if(a.x>0) qq=0;
if(a.x<0) qq=pi;
}
return qq;
}
inline bool check(punct a, punct o, punct b)
{
float h1,h2,h;
h1=unghi(a,o);
h2=unghi(b,o);
h=h1-h2;
if(h<0)h+=2*pi;
if(h<3.14159265) return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
j=0;
for(i=0;i<n;i++)
{
scanf("%f%f",&v[i].x,&v[i].y);
if(v[i].x<v[j].x || ( v[i].x==v[j].x && v[i].y<v[j].y )) j=i;
}
aux=v[0];v[0]=v[j];v[j]=aux;
sort(v+1,v+n,cmp);
q[0]=0;
q[1]=1;
k=2;
for(i=2;i<n;i++)
{
q[k]=i;
ok=check(v[q[k-2]],v[q[k-1]],v[q[k]]);
while(!ok)
{
k--;
q[k]=i;
ok=check(v[q[k-2]],v[q[k-1]],v[q[k]]);
}
k++;
}
//printf("%f %f",(asin(sqrt(3)/2)) ,3.14159265/3);
for(i=0;i<k;i++) printf("%.2f %.2f\n", v[q[i]].x,v[q[i]].y);
return 0;
}