Cod sursa(job #2661598)

Utilizator metallidethantralayerIon Cojocaru metallidethantralayer Data 22 octombrie 2020 12:37:35
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Punct
{
    double x,y,unghi;
} stiva[120005],v[120005],Pct;
int n,h;
double Dreapta(Punct a,Punct b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool Compare(const Punct &a,const Punct &b)
{
    if(a.unghi==b.unghi)
    {
        if(a.unghi<=3.1415/2)
        {
            if(a.y==b.y)
                return a.x<b.x;
            else return a.y<b.y;
        }
        else
        {
            if(a.y==b.y)
                return a.x>b.x;
            else return a.y>b.y;
        }
    }
    return a.unghi<b.unghi;
}
long long int Determinant(Punct a,Punct b,Punct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y;
}
int main()
{
    f>>n;
    Pct.x=1e9+1;
    Pct.y=1e9+1;
    for(int i=1; i<=n; i++)
    {
        f>>v[i].x>>v[i].y;
        if((Pct.y>v[i].y)||(Pct.y==v[i].y&&Pct.x>v[i].x))
            Pct=v[i];
    }
    for(int i=1; i<=n; i++)
        v[i].unghi=acos((v[i].x-Pct.x)/Dreapta(Pct,v[i]));
    sort(v+1,v+n+1,Compare);
    for(int i=1; i<=n; i++)
    {
        stiva[++h]=v[i];
        while(h>2&&Determinant(stiva[h-2],stiva[h-1],stiva[h])<=1e-12)
            stiva[h-1]=stiva[h],h--;
    }
    g<<h<<'\n';
    for(int i=1; i<=h; i++)
        g<<fixed<<setprecision(6)<<stiva[i].x<<' '<<stiva[i].y<<'\n';



    return 0;
}