Cod sursa(job #1131293)

Utilizator meriniucrMeriniuc Razvan- Dumitru meriniucr Data 28 februarie 2014 19:10:26
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <algorithm>
#define x first
#define y second
#include <iostream>

using namespace std;

const double satan=1e-12;

typedef pair<double,double> C;

C coord[120001];
int punct[120001];
bool viz[120001];

int u(int a, int o, int b)
{
    return (coord[a].x - coord[o].x) * (coord[b].y - coord[o].y) - (coord[b].x - coord[o].x) * (coord[a].y - coord[o].y);

}

int main()
{
    ifstream mama("infasuratoare.in");
    ofstream tata("infasuratoare.out");

    int n,i,j,k;

    mama>>n;
    for(i=1;i<=n;i++)
        mama>>coord[i].x>>coord[i].y;
    cout<<u(3,1,2);
    sort(coord+1,coord+n+1);
    punct[1]=1; punct[2]=2;
    i=2;
    viz[1]=true;
    for(j=i+1;j<=n;j++)
    {
        k=j;
        while(k<=n and u(punct[i],punct[i-1],k) - satan < 0)
            k++;
        if(k==n+1) {punct[++i]=j; viz[punct[i-1]]=true;}
            else punct[i]=j;
    }
    viz[n]=true;
    punct[++i]=n-1;

    for(j=n-2;j>1;j--)
    {
        if(!viz[j])
        {   k=j;
            while(k>=1 and u(k,punct[i-1],punct[i]) - satan > 0)
                k--;
            if(k==0) punct[++i]=j;
                else
                punct[i]=j;
        }
    }
    k=punct[i]-1;
    while(k>=1 and u(k,punct[i-1],punct[i]) - satan > 0)
            k--;
    if(k!=1) i--;
    tata<<i+1<<'\n';
    for(j=i+1;j>=1;j--)
        tata<<coord[punct[j]].x<<" "<<coord[punct[j]].y<<'\n';

    return 0;
}