Cod sursa(job #2574483)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 5 martie 2020 22:50:26
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <bits/stdc++.h>
#define DIM 120010
using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
pair <double, double> v[DIM];
int n,i,k;
int d[DIM];
double det (double X1, double Y1, double X2, double Y2, double X3, double Y3){
    return (X2-X1) * (Y3-Y1) - (X3-X1) * (Y2-Y1);
}
double dist (double x, double y, double x2, double y2){
    return (x - x2) * (x - x2) + (y - y2) * (y - y2);
}
int cadran (double x, double y){
    if (x > 0 && y >= 0)
        return 1;
    if (x <= 0 && y > 0)
        return 2;
    if (x < 0 && y >= 0)
        return 3;
    return 4;
}
inline int cmp2 (pair <double,double> a, pair <double,double> b){
    int c = cadran (a.first,a.second), c2 = cadran (b.first,b.second);
    if (c != c2)
        return c < c2;
    double aria = det (0,0,a.first,a.second,b.first,b.second);
    if (!aria)
        return dist (0,0,a.first,a.second) < dist (0,0,a.first,a.second);
    return aria > 0;
}
inline int cmp (pair <double,double> a, pair <double,double> b){
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}
int main (){

    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].first>>v[i].second;

    sort (v+1,v+n+1,cmp);
    double x = v[1].first, y = v[1].second;
    for (i=1;i<=n;i++)
        v[i].first -= x, v[i].second -= y;

    sort (v+1,v+n+1,cmp2);

    for (i=1;i<=n;i++){
        while (k >= 2 && det (v[d[k-1]].first,v[d[k-1]].second,v[d[k]].first,v[d[k]].second,v[i].first,v[i].second) <= 0)
            k--;
        d[++k] = i;
    }
    fout<<k<<"\n";
    for (i=1;i<=k;i++)
        fout<<setprecision(6)<<fixed<<v[d[i]].first+x<<" "<<v[d[i]].second+y<<"\n";

    return 0;
}