Cod sursa(job #2576013)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 6 martie 2020 16:45:02
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define inf 1000000001
#define DIM 120010
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,pmin,i,j,k;
pair<double,double> v[DIM],s[DIM];
double det(const pair<double,double> &a, const pair<double,double> &b, const pair<double,double> &c) {
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp(const pair<double,double> &a, const pair<double,double> &b) {
    double d=det(v[1],a,b);
    if (d!=0)
        return d>0;
    else
        return (a.x*a.x+a.y*a.y)>(b.x*b.x+b.y*b.y);
}
int main() {
    fin>>n;
    v[0].x=v[0].y=inf;
    for (i=1;i<=n;i++) {
        fin>>v[i].x>>v[i].y;
        if (v[i].y<v[pmin].y||(v[i].y==v[pmin].y&&v[i].x<v[pmin].x))
            pmin=i;
    }
    v[0]=v[pmin];
    swap(v[1],v[pmin]);
    sort(v+2,v+n+1,cmp);
    for (j=3;j<=n;j++)
        if (det(v[1],v[2],v[j])!=0.0)
            break;
    i=2, j--;
    while (i<j)
        swap(v[i++],v[j--]);
    s[1]=v[1], s[2]=v[2];
    k=2;
    for (i=3;i<=n;i++) {
        while (k>=2&&det(s[k-1],s[k],v[i])<=0.0)
            k--;
        s[++k]=v[i];
    }
    fout<<k<<"\n";
    for (i=1;i<=k;i++)
        fout<<fixed<<setprecision(6)<<(int)1000000*s[i].x/1000000.0<<" "<<(int)1000000*s[i].y/1000000.0<<"\n";
    return 0;
}