Cod sursa(job #1211239)

Utilizator TibixbAndrei Tiberiu Tibixb Data 22 iulie 2014 10:48:46
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
int n, minim, i, p, k;
struct punct{
    double x;
    double y;
};
punct a[120010], s[120010], aux;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

double det(const punct &a, const punct &b, const punct &c) {
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

int cmp(const punct &p, const punct &q) {
    return det(a[1], p, q)>0;
}

int main(){
    in>>n;
    minim=2000000000;
    for(i=1; i<=n; i++){
        in>>a[i].x>>a[i].y;
        if(a[i].x<minim){
            minim=a[i].x;
            p=i;
        }
    }
    aux=a[1];
    a[1]=a[p];
    a[p]=aux;

    sort(a+2, a+n+1, cmp);

    s[1] = a[1];
    s[2] = a[2];
    k = 2;
    for (i=3;i<=n;i++) {
        while (k>=2 && det(s[k-1], s[k], a[i]) <=0)
            k--;
        s[++k] = a[i];
    }

    out<<k<<"\n";
    for (i=1;i<=k;i++)
        out<<fixed<<setprecision(6)<<s[i].x<<" "<<s[i].y<<"\n";

    return 0;
}