Cod sursa(job #1468399)

Utilizator bogdanmarin69Bogdan Marin bogdanmarin69 Data 5 august 2015 23:09:18
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <algorithm>
using namespace std;
const int MAX = 120001;
struct point{
    double x, y;
} v[MAX];
int n, sus[MAX], jos[MAX], vsus, vjos;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
bool cmp(point a, point b){return a.x<b.x or (a.x==b.x and a.y<b.y);}
double cross(point a, point b, point c){
    return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
int main()
{
    fin>>n;
    for(int i=1; i<=n; i++) fin>>v[i].x>>v[i].y;
    sort(v+1, v+n+1, cmp);
    sus[++vsus] = jos[++vjos] = 1;
    for(int i=2; i<=n; i++)
        if(cross(v[1], v[n], v[i])<0){
            while(vjos>=2 and cross(v[jos[vjos-1]], v[jos[vjos]], v[i])<0)
                vjos--;
            jos[++vjos] = i;
        }
        else{
            while(vsus>=2 and cross(v[sus[vsus-1]], v[sus[vsus]], v[i])>0)
                vsus--;
            sus[++vsus] = i;
        }
    fout.precision(6); fout<<fixed;
    for(int i=1; i<=vjos; i++)
        fout<<v[jos[i]].x<<' '<<v[jos[i]].y<<'\n';
    for(int i=vsus; i>1; i--)
        fout<<v[sus[i]].x<<' '<<v[sus[i]].y<<'\n';
    return 0;
}