Cod sursa(job #448878)

Utilizator space.foldingAdrian Soucup space.folding Data 4 mai 2010 21:58:26
Problema Infasuratoare convexa Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define cxinf 9999999999.99999
#define MAX 120002
using namespace std;

struct point
{
    double x, y;
}P, a[MAX], s[MAX];

void read(point a[], int &n)
{
    P.x=P.y=cxinf;
    fstream fin("infasuratoare.in", ios::in);
    fin>>n;
    for(int i=1; i<=n; ++i)
    {
        fin>>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];
    }
}
void write(point a[], int n)
{
    fstream fout("infasuratoare.out", ios::out);
    setprecision(12);
    fout << setiosflags(ios::fixed) << n+1 << "\n";
    for(int i=0; i<=n; ++i)
        fout << a[i].x << " " << a[i].y << "\n";
}
bool operator<(point A, point B)
{
    return (((A.y-P.y)*(B.x-P.x)-(B.y-P.y)*(A.x-P.x))<0);
}

bool operator!=(point A, point B)
{
    return ((A.x-B.x) || (A.y-B.y));
}

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[], point stack[], int n)
{
    int vertex=2;
    stack[0]=P;
    stack[1]=a[1];
    for(int i=2; i<=n; ++i)
    {
        if(a[i]!=P)
        {
            while(angle(stack[vertex-2], stack[vertex-1], a[i])<0)
                vertex--;
            stack[vertex++]=a[i];
        }
    }
    return vertex;
}

int main()
{

    int n, hn;
    read(a, n);
    sort(a+1, a+n+1);
    a[0]=P;
    hn=hull(a, s, n);
    write(s, hn-1);
    return 0;
}