Cod sursa(job #2876814)

Utilizator traiandobrinDobrin Traian traiandobrin Data 23 martie 2022 17:22:42
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int nmax=120005;
struct point
{
    double x,y;
    bool operator ^(const point & that)const
    {
        return x==that.x&&y==that.y;
    }
    bool operator <(const point &that) const
    {
        return make_pair(x,y)<make_pair(that.x,that.y);
    }
};
point p0;
point p[nmax];
void minn(point &p1,point p2)
{
    if(p2.y<p1.y)
        p1=p2;
        else
    if(p2.x<p1.x&&p1.y==p2.y)
        p1=p2;
}
int cw(point a,point b,point c)
{
    double x=(b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);//-x
    if(x>0)
        return 1;
    if(!x)
        return x;
    return -1;
}
int main()
{
    int n;
    int ind;
    while(cin>>n&&n){
            ind=1;
    for(int i=1;i<=n;++i)
    {
        double a,b;
        cin>>a>>b;
        p[i].x=a;
        p[i].y=b;
        if(i==1)
            p0=p[i];
            point cop=p0;
            p0=min(p0,p[i]);
            if(!(cop^p0))
                ind=i;
    }
    swap(p[1],p[ind]);
    sort(p+2,p+n+1,[&p0](point a,point b)
         {
             int ori=cw(p0,a,b);
             if(ori==0)
                return (a.x-p0.x)*(a.x-p0.x)+(a.y -p0.y)*(a.y-p0.y)<=(b.x-p0.x)*(b.x-p0.x)+(b.y -p0.y)*(b.y-p0.y);
             return ori>0;
         });
         int ans[nmax],vf=2;
         int m=1;
         /*
         for(int i=2;i<=n;++i)
         {
             while(i<n&&!cw(p0,p[i],p[i+1]))++i;
             p[++m]=p[i];
         }
         n=m;*/
    ans[1]=1;
    ans[2]=2;
         for(int i=3;i<=n;++i)
         {
            while((vf>1&&cw(p[ans[vf-1]],p[ans[vf]],p[i])!=1))
            {
                --vf;
            }
                ans[++vf]=i;
         }
         int start=1;
         if(vf==2)
         {
             if(!(p[1]^p[2]))
                cout<<2<<'\n'<<p[1].x<<" "<<p[1].y<<'\n'<<p[2].x<<" "<<p[2].y;
             else
                cout<<1<<'\n'<<p[1].x<<" "<<p[1].y;
             cout<<'\n';
             break;
             continue;
         }
            cout<<vf-start+1<<'\n';
        cout<<fixed<<setprecision(12);
         for(;start<=vf;++start)
            cout<<p[ans[start]].x<<" "<<p[ans[start]].y<<'\n';
            break;
    }
    return 0;
}