Cod sursa(job #2402011)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 10 aprilie 2019 11:50:18
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct point {
    double x, y;
};

point v[120005];
int h[120005];

point ll;

const double eps = 1e-12;

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

bool cmp(point a, point b) {
    if(cp(ll, a, b) > 0)
        return 1;
    return 0;
}

int main()
{
    int n;
    cin >> n;
    
    ll.x = 1e10;
    ll.y = 1e10;

    for(int i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;
        
        if(v[i].y == ll.y && v[i].x < ll.x)
            ll = v[i];
        if(v[i].y < ll.y)
            ll = v[i];
    }    
    
    v[0] = ll;
    //cout << ll.x << " " << ll.y << endl << endl;
    
    int ok = 0;
    for(int i = 1; i <= n; i++) {
        if(v[i].x == ll.x && v[i].y == ll.y)    
            ok = 1;
        if(ok)
            v[i] = v[i+1];
    }
    
    v[n] = ll;
    
    sort(v + 1, v + n, cmp);
    
    int top = 2;
    h[0] = 0;
    h[1] = 1;
    
    //cout << "HERE";
    
    int i = 2;
    while(i <= n) {
        if(cp(v[h[top-1]], v[h[top]], v[i]) > 0) {
            h[++top] = i;
            i++;        
        }
        else
            top--;
    }
    
    cout << top << endl;
    
    for(int i = 0; i < top; i++) {
        cout << v[h[i]].x << " " << v[h[i]].y << endl;
    }
    
    //sort()
}