Cod sursa(job #1131227)

Utilizator a96tudorAvram Tudor a96tudor Data 28 februarie 2014 18:39:15
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define NMAX 120010
#define DIF 1e-12
using namespace std;
vector < pair<double,double> > V;
int St[NMAX],N;
bool used[NMAX];
inline void Write_Data()
{
    printf("%d\n",St[0]);
    for (int i=1;i<=St[0];++i)
        printf("%.6lf %.6lf\n",V[St[i]].x,V[St[i]].y);
}
inline int cmp(double x,double y)
{
    if (x+DIF<y) return 1;
    if (y+DIF<x) return -1;
    return 0;
}
inline int Sign(int p1,int p2,int p3)
{
    double P1,P2,P3,P4,P5,P6,Det;
    P1=V[p1].x * V[p2].y; P2=V[p2].x * V[p3].y; P3=V[p3].x * V[p1].y;
    P4=-(V[p2].y * V[p3].x); P5=-(V[p1].y * V[p2].x); P6=-(V[p3].y * V[p1].x);
    Det=P1+P2+P3+P4+P5+P6;
    return cmp(Det,1);
}
inline void Solve(int N)
{
    int k=2,pas=1,i=3;
    used[2]=true; St[1]=1; St[2]=2;
    while (!used[1])
    {
        while (used[i])
            {if (i==N) pas=-1; i+=pas;}
        while (k>=2 && Sign(St[k-1],St[k],i)==-1)
            used[St[k--]]=false;
        used[i]=true; St[++k]=i;
    }
    St[0]=k;
}
inline void Load_Data(int &N)
{
    double X,Y;
    scanf("%d",&N);
    for (int i=1;i<=N;++i)
        scanf("%lf%lf",&X,&Y), V.pb(mp(X,Y));
    sort(V.begin(),V.end());
    memset(used,false,sizeof(used));
}
int main()
{
    freopen("infasuratoare.in","r",stdin); freopen("infasuratoare.out","w",stdout);
    Load_Data(N);
    Solve(N);
    Write_Data();
    fclose(stdin); fclose(stdout);
    return 0;
}