Cod sursa(job #1142291)

Utilizator RadEmanuelRad Emanuel RadEmanuel Data 13 martie 2014 18:11:09
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define INF 21000000
#define DMAX 12000
using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,spoz,i;
struct punct{double x,y;}st[DMAX],pct;
vector<punct> v;
vector<punct>::iterator it;

int cmp(punct a, punct b)
{
    double m1,m2;
    if(a.x==v[0].x) m1=INF;
               else m1=(a.y-v[0].y)/(a.x-v[0].x);
    if(b.x==v[0].x) m2=INF;
               else m2=(b.y-v[0].y)/(b.x-v[0].x);
    return m1<m2;
}

int calc(punct A, punct B, punct C){return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);}

int main()
{
    fin>>n;
    for(i=0;i<n;++i)
    {
        fin>>pct.x>>pct.y;
        v.push_back(pct);
        if(v[i].x<v[spoz].x || (v[i].x==v[spoz].x && v[i].y<v[spoz].y))
            spoz=i;
    }
    swap(v[0],v[spoz]);
    sort(v.begin()+1,v.end(),cmp);
    st[1]=v[0];
    st[2]=v[1];
    int niv=2;
    for(i=2;i<n;++i)
    {
        while(niv>=2 && calc(st[niv-1],st[niv],v[i])<=0)
            --niv;
        st[++niv]=v[i];
    }
    fout<<niv<<'\n';
    for(i=1;i<=niv;++i)
        fout<<st[i].x<<" "<<st[i].y<<'\n';
    return 0;
}