Cod sursa(job #1473859)

Utilizator tiby10Tibi P tiby10 Data 20 august 2015 12:57:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

typedef pair<double, double> Pair;
#define x first
#define y second
#define NMAX 120005
#define precizie fixed<<setprecision(12)
#define det(Z, X, Y) (1LL*(P[X].x-P[Z].x)*(P[Y].y-P[Z].y)) - (1LL*(P[X].y-P[Z].y)*(P[Y].x-P[Z].x))
Pair P[NMAX];
vector<int> up, down;
int n;

void hull(){
 int i;
 for(i=1; i<=n; i++){
    while(up.size()>=2 && det(up[up.size()-2], up[up.size()-1], i)>=0)
        up.pop_back();
    up.push_back(i);

    while(down.size()>=2 && det(down[down.size()-2], down[down.size()-1], i)<=0)
        down.pop_back();
    down.push_back(i);
 }

 fout<<down.size()-2+up.size()<<'\n'<<precizie;
 for(i=1;i<down.size();i++)
    fout<<P[down[i]].x<<" "<<P[down[i]].y<<'\n';
 for(i=up.size()-2; i; i--)
    fout<<P[up[i]].x<<" "<<P[up[i]].y<<'\n';
 fout<<P[down.front()].x<<" "<<P[down.front()].y;
}

int main() {

    fin>>n;
    int i,x,y;
    for(i=1;i<=n;i++)
        fin>>P[i].x>>P[i].y;

    sort(P+1,P+n+1,[](Pair a, Pair b){
            return a.x<b.x || (a.x==b.x && a.y<b.y);
         });
    hull();
    return 0;
}