Cod sursa(job #2296396)

Utilizator cc4infinityCojocaru Catalin cc4infinity Data 4 decembrie 2018 17:23:21
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct coor
{
    double x;
    double y;
} t[120002];

int i,j,n,m,poz,a,b,v[120003],c[120003];

bool comp(coor a,coor b)
{
    if (a.x>b.x) return 0;
    if (a.x<b.x) return 1;
    if (a.y>b.y) return 0;
    return 1;
}

double det(coor p1,coor p2,coor p3)
{
     return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x;
}

int main()
{
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>t[i].x>>t[i].y;
    sort(t+1,t+n+1,comp);
    v[1]=1;
    v[2]=2;
    c[2]=1;
    poz=2;
    for (i=3;i<=n;i++)
    {
        if (c[i]) continue;
        while (poz>=2 && det(t[v[poz-1]],t[v[poz]],t[i])<0)
            c[v[poz--]]=0;
        poz++;
        v[poz]=i;
        c[i]=1;
    }
    for (i=n;i>1;i--)
    {
        if (c[i]) continue;
        while (poz>=2 && det(t[v[poz-1]],t[v[poz]],t[i])<0)
            c[v[poz--]]=0;
        poz++;
        v[poz]=i;
        c[i]=1;
    }
    fout<<poz<<"\n"<<fixed<<setprecision(6);
    for(i=1;i<=poz;i++)
        fout<<t[v[i]].x<<" "<<t[v[i]].y<<"\n";
    return 0;
}