Cod sursa(job #2321244)

Utilizator triscacezarTrisca Vicol Cezar triscacezar Data 15 ianuarie 2019 21:02:44
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;

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

const double mic=1e-7;

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

double dist(pair<double,double> a,pair<double,double> b)
{
    return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

double det(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
    return (a.first*b.second+c.first*a.second+b.first*c.second-
           (c.first*b.second+a.first*c.second+b.first*a.second));
}

bool comp(pair<int,int> a,pair<int,int> 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)
        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=0;i<=k;i++)
        g<<V[i].first<<' '<<V[i].second<<'\n';
    return 0;
}