Cod sursa(job #2128956)

Utilizator crastanRavariu Eugen crastan Data 12 februarie 2018 12:32:24
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{double x,y;} p[120006],s[120006];
int n,i,nrs=2;
double detr(punct a,punct b,punct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-c.x*b.y-b.x*a.y;
}
bool comp(punct a,punct b)
{
    if(detr(p[0],a,b)>0) return true;
        return false;
}
int main()
{
    fin>>n;
    fin>>p[0].x>>p[0].y;
    for(i=1;i<=n-1;i++)
    {
        fin>>p[i].x>>p[i].y;
        if(p[0].x>p[i].x||(p[0].x==p[i].x&&p[0].y>p[i].y)) swap(p[0],p[i]);
    }
    sort(p+1,p+n,comp);
    s[1]=p[0];
    s[2]=p[1];
    for(i=2;i<n;i++)
    {
        if(detr(s[nrs-1],s[nrs],p[i])>0)
            s[++nrs]=p[i];
        else s[nrs]=p[i];
    }
    fout<<nrs<<'\n';
    for(i=1;i<=nrs;i++)
        fout<<s[i].x<<" "<<s[i].y<<'\n';
    return 0;
}