Cod sursa(job #1830112)

Utilizator DobosDobos Paul Dobos Data 16 decembrie 2016 10:35:02
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <bits/stdc++.h>
#define INF 1e9
#define NMAX 120005
using namespace std;

struct point{
double x,y;
};
point V[NMAX];
int sol[NMAX];

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

inline double unghiularpoint(point a,point b,point c){
    return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
struct cmp{
    int operator()(const point &a,const point &b){
        return unghiularpoint(V[1],a,b) > 0;
    }
};


int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

    int n,poz = 1,top = 0;

    fin >> n;

    for(int i = 1; i <= n; i++){
        fin >> V[i].x >> V[i].y;
        if(V[i].x < V[poz].x)
            poz = i;
        if(V[i].x == V[poz].x && V[i].y < V[poz].y)
            poz = i;
    }
    swap(V[1],V[poz]);
    sort(V +  2,V + n + 1, cmp());
    V[n + 1] = V[1];
    sol[++top] = 1;

    for(int i = 2; i <= n; i++){
        sol[++top] = i;
        while(unghiularpoint(V[sol[top - 1]],V[sol[top]],V[i + 1]) < 0)
            top--;

    }
    fout << top << "\n";

    for(int i = 1; i <= top; i++)
        fout << setprecision(6) << fixed << V[sol[i]].x << " " << V[sol[i]].y << "\n";


    return 0;
}