Cod sursa(job #1844997)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 10 ianuarie 2017 18:56:46
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define ll long double
using namespace std;
ifstream f("infasuratoareconvexa.in");
ofstream g("infasuratoareconvexa.out");
struct point {
    ll x, y;
};
int n,k;
vector<point> v(120005);
vector<point> s(120005);
void citire()
{
    f>>n;
    int i;
    for(i=1;i<=n;i++)
    f>>v[i].x>>v[i].y;
}
ll det(const point& A, const point& B, const point& C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
bool cmp1(point a, point b)
{
    return (a.x<b.x) or ((a.x==b.x) and (a.y<b.y));
}
bool cmp2(const point& p1, const point& p2)
{
    return det(v[1],p1,p2)<0;
}
void sortare()
{
    int pos=1,i;
    for(i=2;i<=n;i++)
        if(cmp1(v[i],v[pos]))
            pos=i;
    swap(v[1],v[pos]);
    sort(v.begin()+2,v.begin()+n+1,cmp2);
}
void solve()
{
    int i;
    sortare();
    k=2;
    s[1]=v[1];
    s[2]=v[2];
    for(i=3;i<=n;i++)
    {
        while(k>=2 and det(s[k-1],s[k],v[i])>0)
            k--;
        s[++k]=v[i];
    }
}

void afisare()
{
    g<<k<<'\n';
    int i;
    for(i=k;i>=1;i--)
    {
        g<<fixed<<setprecision(6)<<s[i].x<<' ';
        g<<fixed<<setprecision(6)<<s[i].y<<'\n';
    }
}
int main()
{
    citire();
    solve();
    afisare();

    return 0;
}