Cod sursa(job #2414785)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 25 aprilie 2019 01:30:52
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

const double kEps=1e-9;

struct pct{
    double x=0,y=0;
} a[120010],b[120010];

int n,i,k;

double DET(pct a,pct b,pct c){
//   a.x  a.y  1
//   b.x  b.y  1
//   c.x  c.y  1
    return (a.x*b.y+a.y*c.x+b.x*c.y)-(c.x*b.y+a.x*c.y+b.x*a.y);
}


int sgn(double val){
    if(abs(val)<kEps)return 0;
    if(val>kEps)return 1;
    return -1;
}

inline double dst(pct A,pct B){
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

bool comp(pct A,pct B){

    double Asin=(A.y-a[1].y)/dst(A,a[1]);
    double Bsin=(B.y-a[1].y)/dst(B,a[1]);
    if(abs(Asin-Bsin)<kEps)
        return dst(A,a[1])<dst(B,a[1]);
    else
        return Asin<Bsin;
}

int main()
{
    f>>n;
    for(i=1;i<=n;i++){
        f>>a[i].x>>a[i].y;
        if(a[i].x<a[1].x||(a[i].x==a[1].x&&a[i].y<a[1].y))
            swap(a[i],a[1]);
    }

    sort(a+2,a+n+1,comp);
    b[1]=a[1];
    b[2]=a[2];k=2;
//    int matr[110][110];
//    memset(matr,0,sizeof(matr));
//    for(i=1;i<=n;i++)
//    {
//        g<<a[i].x<<' '<<a[i].y<<'\n';
//        matr[(int)a[i].y][(int)a[i].x]=i;
//    }
//    for(i=10;i>=0;i--){
//        for(int j=0;j<=10;j++)
//            g<<matr[i][j]<<' ';
//        g<<'\n';
//    }
    for(i=3;i<=n;i++){
        while(k>=2&&sgn(DET(b[k-1],b[k],a[i]))!=1)
            k--;
        b[++k]=a[i];
    }
    g<<k<<'\n';
    for(i=2;i<=k;i++)
        g<<fixed<<setprecision(10)<<b[i].x<<' '<<b[i].y<<'\n';
    g<<fixed<<setprecision(10)<<b[1].x<<' '<<b[1].y<<'\n';
    return 0;
}