Cod sursa(job #1334692)

Utilizator vlad00Vlad Stoleru vlad00 Data 4 februarie 2015 16:26:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int v[120001];
struct punct_t
{
    double x,y;
}minp,punct[120001],rasp[120001];
bool det(punct_t a, punct_t b, punct_t c)
{
    if((a.x*b.y+b.x*c.y+c.x*a.y)-(a.y*b.x+b.y*c.x+c.y*a.x)>0)
        return true;
    else
        return false;
}
bool comp(punct_t a,punct_t b)
{
    if(det(minp,a,b)) return false;
    else return true;
}
int main()
{
    int n,i,j,k=2,poz=0;
    double x,y;
    minp.x=1000000001;
    minp.y=1000000001;
       f>>n;
    for(i=1;i<=n;i++)
        {
            f>>x>>y;
            if(x<minp.x||(x==minp.x && y<minp.y))
            {
                minp.x=x;
                minp.y=y;
                poz=i;
            }
            punct[i].x=x;
            punct[i].y=y;
        }
    swap(punct[poz].x,punct[n].x);
    swap(punct[poz].y,punct[n].y);
    n--;
    sort(punct+1,punct+n+1,comp);
    rasp[1]=minp;
    rasp[2]=punct[1];
    for(i=2;i<=n;i++)
    {
        while(det(rasp[k-1],rasp[k],punct[i]))
        {
            k--;
        }
        rasp[++k].x=punct[i].x;
        rasp[k].y=punct[i].y;
    }
    g<<k<<endl;
    g<<fixed<<setprecision(6)<<rasp[1].x<<' '<<rasp[1].y<<endl;
    for(i=k;i>1;i--)
        g<<fixed<<setprecision(6)<<rasp[i].x<<' '<<rasp[i].y<<endl;
    return 0;
}