Cod sursa(job #1452896)

Utilizator MaarcellKurt Godel Maarcell Data 22 iunie 2015 11:28:33
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;

struct point{
    double x,y;
};

int N; point a[125000],stack[125000];

double c_product(point A,point B,point C){
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

inline bool cmp(point A, point B){
    return c_product(a[1],A,B)<0;
}

int main(){
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fin >> N;

    int i,pos=1;
    for (i=1; i<=N; i++){
        fin >> a[i].x >> a[i].y;
        if (a[i].x<a[pos].x)
            pos=i;
    }
    swap(a[1],a[pos]);
    sort(a+2,a+N+1,cmp);

    stack[1]=a[1];
    stack[2]=a[2];
    int r=2;
    for (i=3; i<=N; i++){
        while (r>=2 && c_product(stack[r-1],stack[r],a[i])>0)
            r--;
        stack[++r]=a[i];
    }

    fout << r << "\n";
    for (i=r; i>0; i--)
        fout << fixed << setprecision(7) << stack[i].x << " " << stack[i].y << "\n";
    return 0;
}