Cod sursa(job #900262)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 28 februarie 2013 18:42:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define x first
#define y second
#define Nmax 120009

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

int n,i,ok[Nmax],q=1;
vector<pair<double,double> > a(Nmax);
vector<int> Q;

double semn(pair<double,double> A,pair<double,double> B,pair<double,double> C)
{
    return A.x*B.y + B.x*C.y + C.x*A.y - A.x*C.y - B.x*A.y - C.x*B.y;
}

int main()
{
    in>>n;
    for (i=1;i<=n;i++)
        in>>a[i].x>>a[i].y;
    sort(a.begin()+1,a.begin()+n+1);

    Q.pb(1);
    Q.pb(2);
    ok[2]=1;
    i=2;

    while (!ok[1])
    {
        while (ok[i])
        {
            if (i==n) q=-1;
            i+=q;
        }

        while (Q.size()>=2 && semn(a[Q[Q.size()-2]],a[Q[Q.size()-1]],a[i])<0)
        {
            ok[Q.back()]=0;
            Q.pop_back();
        }

        Q.push_back(i);
        ok[i]=1;
    }
    Q.pop_back();

    out<<Q.size()<<'\n';
    out.setf(ios::fixed,ios::floatfield);
    out.precision(6);

    for (i=0;i<Q.size();i++)
        out<<a[Q[i]].x<<' '<<a[Q[i]].y<<'\n';
}