Cod sursa(job #2575963)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 6 martie 2020 16:29:36
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>
#define inf INT_MAX
#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> p[DIM],s[DIM];
double det(double X1,double Y1,double X2,double Y2,double X3,double Y3) {
    return (X2-X1)*(Y3-Y1)-(X3-X1)*(Y2-Y1);
}
bool cmp(const pair<double,double> &a, const pair<double,double> &b) {
    double d=det(0,0,a.x,a.y,b.x,b.y);
    if (d!=0)
        return d>0;
    return (a.x*a.x+a.y*a.y)>(b.x*b.x+b.y*b.y);
}
int main() {
    fin>>n;
    p[0]={inf,inf};
    for (i=1;i<=n;i++) {
        fin>>p[i].x>>p[i].y;
        if (p[i].y<p[pmin].y||(p[i].y==p[pmin].y&&p[i].x<p[pmin].x))
            pmin=i;
    }
    p[0]=p[pmin];
    p[pmin]=p[1];
    p[1]=p[0];
    for (i=1;i<=n;i++) {
        p[i].x-=p[0].x;
        p[i].y-=p[0].y;
    }
    sort(p+2,p+n+1,cmp);
    for (j=3;j<=n;j++) {
        if (det(p[1].x,p[1].y,p[2].x,p[2].y,p[j].x,p[j].y))
            break;
    }
    i=2, j--;
    while (i<j)
        swap(p[i++],p[j--]);
    s[1]=p[1], s[2]=p[2];
    k=2;
    for (i=3;i<=n;i++) {
        while (k>=2&&det(s[k-1].x,s[k-1].y,s[k].x,s[k].y,p[i].x,p[i].y)<0)
            k--;
        s[++k]=p[i];
    }
    fout<<k<<"\n";
    for (i=1;i<=k;i++)
        fout<<fixed<<setprecision(6)<<(int)(s[i].x+p[0].x)*1000000/1000000.0<<" "<<(int)(s[i].y+p[0].y)*1000000/1000000.0<<"\n";
    return 0;
}