Cod sursa(job #2759951)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 21 iunie 2021 16:08:52
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>
#define f double
#define x first
#define y second
#define pi 3.14159
using namespace std;

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

pair<f,f> sj={-1,-1};

f angleTo( pair<f,f> o, pair<f,f> p)
{
    return atan2(p.y-o.y,p.x-o.x);
}

bool cmp(const pair<f,f> &a, const pair<f,f> &b)
{
    return (angleTo(sj,a)<angleTo(sj,b))||(angleTo(sj,a)==angleTo(sj,b)&&a.x<b.x);
}


vector<pair<f,f> > infas(vector<pair<f,f> > v)
{
    sort(v.begin(),v.end(),cmp);
    vector<pair<f,f> > ans;

    //cout<<angleTo(sj,{2,0})/pi*180<<'\n';
   // cout<<sj.x<<','<<sj.y<<'\n';
    //for(int i=0;i<v.size();i++)
    //    cout<<v[i].x<<','<<v[i].y<<' ';
    //cout<<'\n';
    ans.push_back(sj); ans.push_back(v[0]);

    for(int i=1;i<v.size();i++)
    {
        pair<f,f> p1=ans[ans.size()-1],p2=ans[ans.size()-2];
       while(ans.size()>1&&angleTo(p1,p2)>angleTo(p2,v[i]))
       {
           //cout<<angleTo(p1,p2)<<' '<<angleTo(p2,v[i])<<' '<<p1.x<<','<<p1.y<<' '<<p2.x<<','<<p2.y<<' '<<v[i].x<<','<<v[i].y<<'\n';
           ans.pop_back();
           p1=p2;
           if(ans.size()>1) p2=ans[ans.size()-2];
       }
       ans.push_back(v[i]);
    }
    return ans;

}

int main()
{
    int n;
    vector<pair<f,f> > pts;
    int sjpos;
    in>>n;
    for(int i=0;i<n;i++)
    {
        pair<f,f> pt;
        in>>pt.x>>pt.y;
        pts.push_back(pt);
        if(pt.x<sj.x||i==0) {sj=pt; sjpos=i;}
        if(pt.x==sj.x&&pt.y<sj.y) {sj=pt; sjpos=i;}
    }

    for(int i=0;i<n;i++)
    {
        if(i>sjpos) pts[i-1]=pts[i];
    }
    pts.pop_back();
    pts=infas(pts);
    out<<pts.size()<<'\n';
    for(int i=0;i<pts.size();i++)
    {
        out<<fixed<<setprecision(6)<<pts[i].x<<' '<<pts[i].y<<'\n';
    }
    return 0;
}