Cod sursa(job #1920099)

Utilizator KronSabau Valeriu Kron Data 9 martie 2017 22:27:31
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 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 (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

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


int main()
{
f >> n;
    int ind;
    point mn;
    f>>mn.x>>mn.y;
    p[1].x=mn.x;
    p[1].y=mn.y;
    for(int i=2;i<=n;i++)
    {
        f>>p[i].x>>p[i].y;
        if(mn.x>p[i].x || (mn.x==p[i].x && mn.y>p[i].y))
        {
            mn=p[i];
            ind=i;
        }
    }
    swap(p[ind],p[1]);
    sort(p+2,p+n+1,cmp);
    int top=2;
    st[1]=p[1];
    st[2]=p[2];
    for(int i=3;i<=n;i++)
    {

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