Cod sursa(job #2552569)

Utilizator razvanmihailaMihaila Razvan razvanmihaila Data 20 februarie 2020 22:56:16
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include<bits/stdc++.h>
#define nmax 120001
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int n, topleft, topright;
struct coord {
    double x,y;
} v[nmax], jos ,sus ,stleft[nmax], stright[nmax];

double arie(coord a,coord b,coord c) {
    double q = a.x * (b.y - c.y) - b.x * (a.y - c.y) + c.x * (a.y - b.y);
    if(q > 0)
        return 1;
    else
        if(q < 0)
        return -1;
    return 0;
}
bool cmp(coord x,coord y) {
    if(x.y < y.y)
        return true;
    else
     if(x.y == y.y && x.x < y.x)
        return true;
    else
        return false;
}
int main(){

    fin >> n;
    jos.x = jos.y = 2000000000;
    sus.y = sus.x = -1000000000;

    for(int i = 1; i <= n; i ++)
        {
        fin >> v[i].x >> v[i].y;
        if(v[i].y < jos.y || (v[i].y == jos.y && v[i].x < jos.x))
            jos = v[i];
        if(v[i].y > sus.y || (v[i].y == sus.y && v[i].x > sus.x))
            sus = v[i];
    }
    sort(v + 1, v + n + 1, cmp);

    topleft = topright = 1;
    stleft[topleft] = v[1];
    stright[topright] = v[1];

    for(int i = 2; i <= n; i ++)
        {
        if(arie(jos, sus, v[i]) >= 0){
            while(arie(stleft[topleft - 1], stleft[topleft], v[i]) != -1 && topleft > 1)
                topleft --;
            stleft[++ topleft] = v[i];
        }
        if(arie(jos, sus, v[i]) <= 0){
            while(arie(stright[topright - 1], stright[topright], v[i]) != 1 && topright > 1)
                topright --;
            stright[++ topright] = v[i];
        }
    }

    fout << setprecision(6) << fixed;
    fout << topright + topleft - 2 << '\n';

    for(int i = 1; i <= topright; i ++)
        fout << stright[i].x << " " << stright[i].y << '\n';
    for(int i = topleft - 1; i > 1; i --)
        fout<< stleft[i].x<< " " << stleft[i].y << '\n';
    return 0;
}