Cod sursa(job #1473823)

Utilizator tiby10Tibi P tiby10 Data 20 august 2015 12:03:26
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 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 pb push_back
#define pp pop_back
#define precizie fixed<<setprecision(6)
Pair P[NMAX];
vector<int> up;
vector<int> down;
int n;

int det(int i1, int i2, int i3){
 int dx1 = P[i2].x-P[i1].x,
     dx2 = P[i3].x-P[i1].x,
     dy1 = P[i2].y-P[i1].y,
     dy2 = P[i3].y-P[i1].y;
 return (1LL*dx1*dy2)-(1LL*dy1*dx2);
}

void insereaza(vector<int> &v, int i, bool up){
while(v.size()>=2){
    double d = det(v[v.size()-2], v.back(), i);
    if((up && d>0) || (!up && d<0))
        v.pp();
    else break;
}
v.pb(i);
}

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

int main() {

    fin>>n;
    int i;
    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;
}