Cod sursa(job #2661595)

Utilizator metallidethantralayerIon Cojocaru metallidethantralayer Data 22 octombrie 2020 12:28:08
Problema Infasuratoare convexa Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 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)
            return a.x>b.x;
        else return a.x<b.x;
    }
    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>3&&Determinant(stiva[h-2],stiva[h-1],stiva[h])<=0)
        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;
}