Cod sursa(job #2759956)

Utilizator Botnaru_VictorBotnaru Victor Botnaru_Victor Data 21 iunie 2021 16:57:55
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 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;

f orietation(pair<f,f> a, pair<f,f> b, pair<f,f> c)
{
    return (b.y-a.y)*(c.x-b.x)-(c.y-b.y)*(b.x-a.x);
}

bool cmp(const pair<f,f> &a, const pair<f,f> &b)
{
    return orietation(sj,a,b)<0;
}


vector<pair<f,f> > infas(vector<pair<f,f> > v)
{
    sort(v.begin(),v.end(),cmp);
    vector<pair<f,f> > ans;
    ans.push_back(sj); ans.push_back(v[0]);

    for(int i=1;i<v.size();i++)
    {
        pair<f,f> p1=ans[ans.size()-2],p2=ans[ans.size()-1];
       while(ans.size()>1&&orietation(p1,p2,v[i])>0)
       {
           ans.pop_back();
           p2=p1;
           if(ans.size()>1) p1=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;
}