Cod sursa(job #2380896)

Utilizator butasebiButa Gabriel-Sebastian butasebi Data 15 martie 2019 17:11:30
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.64 kb
#include <bits/stdc++.h>
using namespace std;
struct punct
{
    long double x, y;
}v[120005], minn, val1, val2, w[120005];
int cadran(punct a)
{
    if(a.x > minn. x && a.y >= minn.y)return 1;
    if(a.x <= minn.x && a.y  > minn.y)return 2;
    if(a.x <  minn.x && a.y <= minn.y)return 3;
    if(a.x >= minn.x && a.y  < minn.y)return 4;
}
int aria(punct a, punct b, punct c)
{
    return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}
bool cmp(punct a, punct b)
{
    int c1 = cadran(a);
    int c2 = cadran(b);
    if(c1 == c2)
    {
        int det = aria(minn, a, b);
        if(det < 0)return false;
        return true;
    }
    return c1 < c2;
}
bool stanga(punct a, punct b, punct c)
{
    val1.x = b.x - a.x;
    val1.y = b.y - a.y;
    val2.x = c.x - a.x;
    val2.y = c.y - a.y;
    int rez = val1.x * val2.y - val1.y * val2.x;
    if(rez > 0)return true;
    return false;
}
int n, i, k;
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f >> n;
    for(i = 1; i <= n; i ++)
    {
        f >> v[i].x >> v[i].y;
        if(v[i].y < minn.y)minn = v[i];
        else if(v[i].y == minn.y && v[i].x < minn.x)minn = v[i];
    }
    sort(v + 1, v + n + 1, cmp);
    v[n + 1] = v[1];
    w[1] = v[1];
    w[2] = v[2];
    k = 2;
    i = 2;
    while(w[k].x != v[1].x || w[k].y != v[1].y)
    {
        i++;
        while(k > 1 && !stanga(v[i], w[k - 1], w[k]))k--;
        w[++k] = v[i];
    }
    g << k - 1 << "\n";
    for(i = 1; i < k; i ++)
        g << setprecision(12) << fixed << w[i].x << " " << w[i].y << "\n";
    return 0;
}