Cod sursa(job #1723628)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 1 iulie 2016 04:12:31
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>
using namespace std;

const double EPS = 1.e-12;
const int   NMAX = 120005;

struct PII {
    double x, y;

    bool operator<(PII arg) const {
        if(abs(x - arg.x) < EPS)
            return y < arg.y;
        else
            return x < arg.x;
    }
};

int sccw(PII a, PII b, PII c) {
    double s = (b.x-a.x)*(c.y-b.y)-(b.y-a.y)*(c.x-b.x);
    if(abs(s) < EPS)
        return 0;
    if(s>=EPS)
        return 1;
    else
        return -1;
}

PII v[NMAX];
vector<int> upper, lower;

int main(void) {
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n;

    scanf("%d",&n);
    for(int i=0; i<n; ++i)
        scanf("%lf%lf",&v[i].x,&v[i].y);

    sort(v, v+n);

    for(int i=0; i<n; ++i) {
        while(upper.size()>1 && sccw(v[upper[upper.size()-2]], v[upper[upper.size()-1]], v[i])<0)
            upper.pop_back();
        upper.push_back(i);
    }

    for(int i=0; i<n; ++i) {
        while(lower.size()>1 && sccw(v[lower[lower.size()-2]], v[lower[lower.size()-1]], v[i])>0)
            lower.pop_back();
        lower.push_back(i);
    }


    printf("%d\n",upper.size()+lower.size()-2);
    for(int i=0; i<upper.size(); ++i)
        printf("%.6f %.6f\n",v[upper[i]].x,v[upper[i]].y);
    for(int i=lower.size()-2; i>0; --i)
        printf("%.6f %.6f\n",v[lower[i]].x,v[lower[i]].y);

    fclose(stdin);
    fclose(stdout);
    return 0;
}