Cod sursa(job #448907)

Utilizator space.foldingAdrian Soucup space.folding Data 4 mai 2010 22:39:26
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <algorithm>
#define cxinf 999999999.99999
#define MAX 120002
using namespace std;
struct point
{
    double x, y;
}P, a[MAX];
void read(point a[], int &n)
{
    P.x=P.y=cxinf;
    FILE *in=fopen("infasuratoare.in", "r");
    fscanf(in, "%d", &n);
    for(int i=0; i<n; ++i)
    {
        fscanf(in, "%lf%lf", &a[i].x, &a[i].y);
        if(P.x>a[i].x || (P.x==a[i].x && P.y>a[i].y))
        {
            P=a[i];
            swap(a[0], a[i]);
        }
    }
}
void write(point a[], int n)
{
    FILE *out=fopen("infasuratoare.out", "w");
    fprintf(out, "%d\n", n);
    for(int i=0; i<n; ++i)
        fprintf(out, "%.6lf %.6lf\n", a[i].x, a[i].y);
}

bool operator<(point A, point B)
{
    return (((A.y-P.y)*(B.x-P.x)-(B.y-P.y)*(A.x-P.x))<0);
}
double angle(point p1, point p2, point p3)
{
    return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
int hull(point a[], int n)
{
    int vertex=2;
    for(int i=2; i<n; ++i)
    {
            while(angle(a[vertex-2], a[vertex-1], a[i])<0)
                vertex--;
            a[vertex++]=a[i];
    }
    return vertex;
}
int main()
{
    int n, hn;
    read(a, n);
    sort(a+1, a+n);
    hn=hull(a, n);
    write(a, hn);
    return 0;
}