Cod sursa(job #920512)

Utilizator The_DisturbedBungiu Alexandru The_Disturbed Data 20 martie 2013 15:35:01
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.97 kb
#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
#define err 0.000000000001
using namespace std;
struct punct 
{
    double x,y;
}v[120000],aux;
int m,n,i,j,k,q[120000];
bool ok;
inline double panta(double x1, double y1, double x2, double y2)
{
    if(x2-x1<err) return 2000000000;
    return((y2-y1)/(x2-x1));
}
inline double mm(double 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 double unghi(punct a, punct o)
{
    a.x-=o.x;a.y-=o.y;
    double 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)<err)
    {
        if(a.y>0) qq=pi/2;
        if(a.y<0) qq=3*pi/2;
    }
    if(mm(a.y)<err)
    {
        if(a.x>0) qq=0;
        if(a.x<0) qq=pi;
    }
    return qq;
}
inline bool check(punct a, punct o, punct b)
{
    double h1,h2,h;
    h1=unghi(a,o);
    h2=unghi(b,o);
    h=h1-h2;
    if(h<0)h+=2*pi;
    if(h<pi) 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("%lf%lf",&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("%d\n",k);
    for(i=0;i<k;i++) printf("%.12lf %.12lf\n", v[q[i]].x,v[q[i]].y);
    return 0;
}