Cod sursa(job #1976434)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 3 mai 2017 13:45:59
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
#define DIM 120005
#define eps 0.0000000000001
using namespace std;
int n, i, u, j;
int s[DIM];
pair<double, double> v[DIM];
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
double det(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3){
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
int cmp(pair<double, double> a, pair<double, double> b){
    return det(v[1], a, b) > eps;
}
int main(){
    fin>> n;
    j = 0;
    v[0] = make_pair(1000000000, 1000000000);
    for(i = 1; i <= n; i++){
        fin>> v[i].x >> v[i].y;
        if(v[i].y < v[j].y){
            j = i;
        }
    }
    swap(v[1], v[j]);
    sort(v + 2, v + n + 1, cmp);
    s[1] = 1;
    s[2] = 2;
    u = 2;
    for(i = 3; i <= n; i++){
        while(u >= 2 && det(v[i], v[ s[u] ], v[ s[u - 1] ]) > eps){
            u--;
        }
        s[++u] = i;
    }
    fout<< u <<"\n";
    for(i = 1; i <= u; i++){
        fout<< setprecision(6) << fixed << v[ s[i] ].x <<" ";
        fout<< setprecision(6) << fixed << v[ s[i] ].y <<"\n";
    }
    return 0;
}