Cod sursa(job #1452989)

Utilizator cojocarugabiReality cojocarugabi Data 22 iunie 2015 15:54:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
# include <bits/stdc++.h>
# define x first
# define x1 first
# define y1 second
# define y second.first
# define z second.second
# define f fixed << setprecision(6)
# define pii pair < double , pair < double , double > >
const double inf = 1e9;
using namespace std;
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
pii s[120005];
pii d[120005];
bool cmp(pii a,pii b)
{
    return a.z < b.z;
}
double det(double x1,double x2,double x3,double y1,double y2,double y3)
{
    return x1*y2 + y1*x3 + x2*y3 - y2*x3 - y3*x1 - y1*x2;
}
int main(void)
{
    int n;
    fi>>n;
    pair < double , double > mn;
    mn.x1 = mn.y1 = inf;
    for (int i = 1;i <= n;++i) fi>>s[i].x>>s[i].y;
    for (int i = 1;i <= n;++i)
    {
        if (mn.x1 > s[i].x or (mn.x1 == s[i].x && mn.y1 > s[i].y)) mn.x1 = s[i].x,mn.y1 = s[i].y;
    }
    for (int i = 1;i <= n;++i)
        if (mn.x1 != s[i].x) s[i].z = (s[i].y - mn.y1) / (s[i].x - mn.x1);
        else if (mn.x1 == s[i].x && mn.y1 < s[i].y) s[i].z = inf;else s[i].z = -inf;
    sort(s+1,s+1+n,cmp);
    int dist = 2;
    d[1] = s[1];d[2] = s[2];
    for (int i = 3;i <= n;++i)
    {
        while (det(d[dist-1].x,d[dist].x,s[i].x,d[dist-1].y,d[dist].y,s[i].y) < 0 && dist >= 2) --dist;
        d[++dist] = s[i];
    }
    fo << dist << '\n';
    for (int i = 1;i <= dist;++i) fo << f << d[i].x << ' ' << d[i].y << '\n';
    return 0;
}