Cod sursa(job #2371300)

Utilizator dragossofiaSofia Dragos dragossofia Data 6 martie 2019 17:05:25
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
stack <int> q;
struct pct
{
    double x,y;
    double tg;
} a[120001];
int n;
void citire()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>a[i].x>>a[i].y;

    }
}
bool comp(pct a,pct b)
{
    return a.x < b.x||(a.x == b.x && a.y < b.y);

}
bool orientare(pct a,pct b,pct c)
{
    return (a.y - b.y)*(a.x -c .x)<(a.x - b.x)*(a.y - c.y);
}
bool comppant(pct c, pct d)
{
    return orientare(a[1],c,d);
}
int main()
{
    citire();
    sort(a+1,a+n+1,comp);
    sort(a+2,a+n+1,comppant);
    q.push(1);
    q.push(2);
    int x,y;
    for(int i=3; i<=n; i++)
        {y=q.top();
         q.pop();
         x=q.top();
         q.pop();
         while(orientare(a[x],a[y],a[i])==false)
            {y=x;
             x=q.top();
             q.pop();
            }
        q.push(x);
        q.push(y);
        q.push(i);
        }
    fout<<q.size()<<"\n";
    while(q.empty()==false)
        {fout<<fixed<<setprecision(6)<<a[q.top()].x<<" "<<a[q.top()].y<<"\n";
         q.pop();
        }
    return 0;
}