Cod sursa(job #1151184)

Utilizator Walrus21andrei Walrus21 Data 23 martie 2014 21:48:20
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define NM 120005
#define mxy 1000000001
#define PI 3.141592653

using namespace std;

FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");

struct p{float x;float y;};

int i,N;
bool b[NM];
float c1,c2;
p A0,v[NM],st[NM];

float d(p i,p j)
{
    return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y));
}

bool ung(p i,p j,p k)
{
    return i.x*j.y+j.x*k.y+k.x*i.y-i.x*k.y-j.x*i.y-k.x*j.y>0;
}

bool cmp(p i,p j)
{
    float c1,c2;
    c1=acos((i.x-A0.x)/d(A0,i));
    c2=acos((j.x-A0.x)/d(A0,j));
    if(c1==c2) return d(A0,i)<d(A0,j);
    return c1<c2;
}

int main()
{
    fscanf(f,"%d",&N);
    A0.x=A0.y=mxy; int ii;
    for(i=1;i<=N;i++)
    {
        fscanf(f,"%f%f",&v[i].x,&v[i].y);
        if(v[i].y<A0.y) {A0.x=v[i].x; A0.y=v[i].y; ii=i;}
        if(v[i].y==A0.y&&v[i].x<A0.x) {A0.x=v[i].x; ii=i;}
    }
    v[ii].x=v[ii].y=0;
    stable_sort(v+1,v+N+1,cmp);
    for(i=1;i<=N;i++)
    {
        c1=acos((v[i].x-A0.x)/d(A0,v[i]));
        c2=acos((v[i+1].x-A0.x)/d(A0,v[i+1]));
        if(c1==c2) b[i]=1;
    }
    st[0]=A0;
    i=1; while(b[i]) i++;
    st[1]=v[i]; i++;
    while(b[i]) i++;
    st[2]=v[i]; i++;
    int u(2);
    for(;i<=N;i++)
     if(!b[i])
     {
        while(ung(v[i],st[u],st[u-1])) u--;
        st[++u]=v[i];
     }
    fprintf(g,"%d\n",u+1);
    for(i=0;i<=u;i++)
     fprintf(g,"%f %f\n",st[i].x,st[i].y);
    return 0;
}