Cod sursa(job #950413)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 16 mai 2013 19:35:02
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define x first
#define y second
#define mp make_pair
#define pdd pair<double,double>
#define LE 100666
#include <iomanip>
#define inf 1<<26
#include <algorithm>

pdd X[LE],cover[LE];
int i,n,posx,K;
double ymin=inf;
double cross(pdd i1,pdd i2,pdd i3)
{
    i2.x-=i1.x,i2.y-=i1.y;
    i3.x-=i1.x,i3.y-=i1.y;
    i3.x-=i2.x,i3.y-=i2.y;
    return ((i2.x*i3.y)-(i3.x*i2.y));
}
bool comp(pdd i1,pdd i2)
{
    if (cross (X[n+1],i1,i2)<0)return true;
    return false;
}

int main()
{
    f>>n;
    for(i=1; i<=n; ++i) {
        f>>X[i].x>>X[i].y;
        if (X[i].y<ymin) {
            ymin=X[i].y;
            posx=i;
        }
    }

    swap(X[posx],X[n]);
    --n;

    cover[++K]=X[n+1];
    sort(X+1,X+n+1,comp);

    cover[++K]=X[1];

    for(i=2;i<=n;++i)
    {
       while (K>1&&cross(cover[K-1],cover[K],X[i])>0)
         --K;
      cover[++K]=X[i];
    }
  g<<fixed;
  g<<setprecision(6);
    g<<K<<'\n';
    for(i=K;i>=1;--i)
      g<<cover[i].x<<" "<<cover[i].y<<'\n';

    f.close();
    g.close();
    return 0;
}