Cod sursa(job #1704331)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 18 mai 2016 16:54:45
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
using namespace std;

const double eps = 1.e-12;

struct POINT {
    double x, y;
} c;

int sccw(POINT a, POINT b, POINT 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;
}
bool cmp(POINT a, POINT b) {
    return sccw(c, a, b) >= 1;
}

POINT v[120005],
    cvc[120005];

int main(void) {
    FILE *fi = fopen("infasuratoare.in", "r");
    FILE *fo = fopen("infasuratoare.out", "w");
    int n, c_index, c_top;

    fscanf(fi,"%d",&n);
    fscanf(fi,"%lf%lf",&v[0].x,&v[0].y);
    c_index = 0;

    for(int i=1; i<n; ++i) {
        fscanf(fi,"%lf%lf",&v[i].x,&v[i].y);
        if(c.x-eps>=v[i].x)
            c_index = i;
        else if(abs(c.x-v[i].x)<eps && c.y-eps>=v[i].y)
            c_index = i;
    }
    c = v[c_index];
    swap(v[0], v[c_index]);
    sort(v+1,v+n,cmp);

    cvc[0] = c;
    cvc[1] = v[1];
    c_top  = 1;

    for(int i=2; i<n; ++i) {
        if(i==c_index)
            continue;
        while(c_top && sccw(cvc[c_top-1], cvc[c_top], v[i])<0)
            --c_top;
        cvc[++c_top] = v[i];
    }

    fprintf(fo,"%d\n",++c_top);
    for(int i=0; i<c_top; ++i)
        fprintf(fo,"%f %f\n",cvc[i].x,cvc[i].y);

    fclose(fi);
    fclose(fo);
    return 0;
}