Cod sursa(job #416108)

Utilizator recviemAlexandru Pana recviem Data 12 martie 2010 10:37:18
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <cstdio>
#include <algorithm>
#include <math.h>
#define NMAX 100000

typedef struct{
    double x, y;
}point;

point p[NMAX], rez[NMAX];
int n, rC;

void readPoints(){
    FILE* f = fopen("infasuratoare.in","r");
    fscanf(f, "%d", &n);
    int min = 0;
    for (int i = 0; i < n; i++){
        fscanf(f,"%lf %lf", &p[i].x, &p[i].y);
        if (p[i].y < p[min].y || p[i].y == p[min].y && p[i].x < p[i].y)
            min = i;
    }
    point aux = p[min];
    p[min] = p[0];
    p[0] = aux;
}

void writePoints(){
    freopen("infasuratoare.out", "w", stdout);
    printf("%d\n", rC);
    for (int i = 1; i<=rC; i++)
        printf("%lf %lf\n", rez[i].x, rez[i].y);
}

int operator<(point a, point b){
    //return atan2(a.y - p[0].y, a.x - p[0].x) < atan2(b.y - p[0].y, b.x - p[0].x);
    return (a.x-p[0].x)*(b.y-p[0].y) - (a.y-p[0].y)*(b.x-p[0].x)>0;
}

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

void grahamScan(){
    // sort by X and then by Y
    std::sort(p+1, p+n);
    p[n] = p[0];
    rC = 0;
    rez[++rC] = p[0];
    rez[++rC] = p[1];
    for (int i = 2; i<n; i++){
        while (ccw(rez[rC-1], rez[rC], p[i]) <= 0)
            rC--;
        rez[++rC] = p[i];
    }
}

int main(int argc, char* argv[]){
    readPoints();
    grahamScan();
    for (int i=0; i<n; i++)
        printf("%lf %lf\n", p[i].x, p[i].y);
    writePoints();
    //getchar();
    return 0;
}