Cod sursa(job #1921693)

Utilizator raulrusu99Raul Rusu raulrusu99 Data 10 martie 2017 13:54:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

struct point
{
    double x;
    double y;
};

int n, vf;
point st[120005], p[120005], P;

double det(point p1, point p2, point p3)
{
    return (p1.x * p2.y + p1.y * p3.x + p2.x * p3.y - p2.y * p3.x - p3.y * p1.x - p1.y * p2.x);
}

bool cmp(point a, point b)
{
    return det(p[0], a, b) >= 0;
}
int main()
{
    int poz;
    f >> n;
    point a, b, c;
    P.x = 1000000000;
    P.y = 1000000000;

    for(int i = 0; i < n; i++)
    {
        f >> p[i].x >> p[i].y;
        if(P.x > p[i].x)
        {
            P.x = p[i].x;
            P.y = p[i].y;
            poz = i;
        }
        else if(P.x == P.y)
        {
            if(P.y > p[i].y)
            {
                P.x = p[i].x;
                P.y = p[i].y;
                poz = i;
            }
        }
    }
    swap(p[poz], p[0]);
    sort(p+1,p+n,cmp);

    st[0] = p[0];
    st[1] = p[1];
    vf = 1;
    p[n] = p[0];

    for(int i = 2; i <= n; i++)
    {
        while(vf > 0 && det(st[vf - 1], st[vf], p[i]) < 0) vf--;
        st[++vf] = p[i];
    }
    g << vf <<"\n";
    for(int i = 0; i < vf; i++)
    {
        g << fixed << st[i].x <<" "<< st[i].y<<"\n";
    }

    return 0;
}