Cod sursa(job #1647898)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 10 martie 2016 22:41:09
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <iomanip>
#include <stack>
#include <cstring>
#include <fstream>

#define NMax 120005
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct pct{
    double x,y;
}v[NMax];

int n,m,x,y,nr,top,index;
int s[NMax];

double unghi(pct A, pct B, pct C){
    return ((B.y - A.y)*(C.x - A.x) - (C.y - A.y)*(B.x - A.x));
}
bool cmp(pct x, pct y){
    return (unghi(v[1],x,y) > 0);
}
int main()
{
    f >> n;
    int mnx = INF, mny = INF;
    for(int i = 1; i <= n; ++i){
        f >> v[i].x >> v[i].y;
        if(v[i].x < mnx || (v[i].x == mnx && v[i].y < mny)){
            mnx = v[i].x;
            mny = v[i].y;
            index = i;
        }
    }
    swap(v[1],v[index]);
    sort(v + 2, v + 1 + n, cmp);
    s[1] = 1;
    s[2] = 2;
    top = 2;
    for(int i = 3; i <= n; ++i){
        while(unghi(v[s[top - 1]],v[s[top]],v[i]) < 0)
            top--;
        s[++top] = i;
    }
    g << top <<'\n';
    for(int i = top; i >= 1; --i){
        g << fixed << setprecision(6) << v[s[i]].x <<" " << v[s[i]].y <<"\n";
    }
    return 0;
}