Cod sursa(job #1919986)

Utilizator KronSabau Valeriu Kron Data 9 martie 2017 21:52:59
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
     double x,y;
}p[120010],st[120010];
int n,Min;
double det(point a,point b,point c)
{
    return  (a.y-b.y)*(b.x-c.x)-(b.y-c.y)*(a.x-b.x);
}

int cmp(point a,point b)
{
    return det(p[1],a,b)>0;
}


int main()
{
    f >> n;
    Min=1;
    for(int i=1;i<=n;i++)
    {
        f >> p[i].x >> p[i].y;
        if(p[i].x<p[Min].x)
            Min=i;
        if(p[i].x == p[Min].x && p[i].y <p[Min].y)
            Min=i;
    }
    swap(p[Min],p[1]);
    sort(p+1,p+n+1,cmp);
    p[n+1]=p[1];
    int top=0;
    st[++top]=p[1];
    for(int i=2;i<=n;i++)
    {
        st[++top]=p[i];
        while(top>0 && det(st[top-1],st[top],p[i+1])<0)
            top--;
    }
    g << fixed << setprecision(6) <<top << "\n";
    for(int i=1;i<=top;i++)
        g << st[i].x << " " << st[i].y << "\n";
    return 0;
}