Cod sursa(job #3141865)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 17 iulie 2023 11:00:02
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double K,L,ans=1e9;
struct point
{
    double x,y;
} v[200005],start;
vector<point> hull;
double aria(point a,point b,point c)
{
    a.x-=c.x;
    a.y-=c.y;
    b.x-=c.x;
    a.y-=c.y;
    return (a.x*b.y-a.y*b.x);
}
bool comp(point a,point b)
{
    if(a.x==start.x&&a.y==start.y)
        return 1;
    if(b.x==start.x&&b.y==start.y)
        return 0;
    double ar=aria(start,a,b);
    if(ar!=0)
        return ar<0;
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}
double dist(point A,point B)
{
    return sqrt(1.0L*((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)));
}
double unghi(point B,point A,point C)
{
    double a=dist(B,C);
    double b=dist(A,C);
    double c=dist(A,B);
    double u=(b*b+c*c-a*a)/(2.0*b*c);
    u=acos(u);
    return u;
}
void check(double xx, double yy)
{
    point p={xx,yy};
    if(xx<-L||xx>L||yy<-L||yy>L)
        return;
    double maxim=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            double u=unghi(v[i],p,v[j]);
            maxim=max(maxim,u);
        }
    ans=min(ans,maxim);
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fin>>n;
    if(n==1)
    {
        fout<<0;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        if(i==1)
            start=v[i];
        if(v[i].x<start.x)
            start=v[i];
        else if(v[i].x==start.x&&v[i].y<start.y)
            start=v[i];
    }
    sort(v+1,v+n+1,comp);
    for(int i=1;i<=n;i++)
    {
        while(hull.size()>=2)
        {
            int lg=hull.size();
            double ar=aria(hull[lg-2],hull[lg-1],v[i]);
            if(ar>0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(v[i]);
    }
    fout<<hull.size()<<'\n';
    for(auto i:hull)
        fout<<fixed<<setprecision(12)<<i.x<<' '<<i.y<<'\n';
    return 0;
}