Cod sursa(job #2321256)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 15 ianuarie 2019 21:17:24
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
#define det(A,B,C) A.first*B.second+B.first*C.second+C.first*A.second-A.second*B.first-B.second*C.first-C.second*A.first
#define dist(A,B) (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second)

using namespace std;

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

const double mic=0.00000001;

int n,i,j,iq,k;
double u,v;
pair<double,double> Q,P[120010],V[120010];

bool comp(pair<double,double> a,pair<double,double> b)
{
    double val=det(P[0],a,b);
    if(val> mic)return 1;
    if(val<-mic)return 0;
    double X=dist(P[0],a),Y=dist(P[0],b);
    if(X-Y>mic)
        return 0;
    return 1;
}

int main()
{
    f>>n;
    f>>u>>v;
    P[0]={u,v};
    Q=P[0],iq=0;
    for(i=1;i<n;i++)
    {
        f>>P[i].first>>P[i].second;
        if(P[i]<Q)
            Q=P[i],iq=i;
    }
    P[iq]=P[0];P[0]=Q;
    sort(P+1,P+n,comp);
    V[0]=P[0],V[1]=P[1],k=1;
    for(i=2;i<n;i++)
    {
        while(k&&det(V[k-1],V[k],P[i])<-mic)
            k--;
        V[++k]=P[i];
    }
    g<<k+1<<'\n';
    for(i=1;i<=k;i++)
        g<<fixed<<setprecision(10)<<V[i].first<<' '<<V[i].second<<'\n';
    g<<fixed<<setprecision(10)<<V[0].first<<' '<<V[0].second;
    return 0;
}