Cod sursa(job #401864)

Utilizator cristiprgPrigoana Cristian cristiprg Data 23 februarie 2010 10:10:36
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <cstdio>
#include <algorithm>

using namespace std;
#define DIM 120005

struct punct
{
    double x, y;
} v[DIM], first;

int n;

void swap(int &a, int &b)
{
	int aux = a;
	a = b;
	b = aux;
}

double dist(punct A, punct B)
{
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

int directie(punct A, punct B, punct C)
{
    double d = (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
    if (d == 0) //coliniare
        return 0;
    if (d < 0) //dreapta
        return -1;
    //stanga
        return 1;

    printf ("WTF?\n");

}

int fcmp(punct A, punct B)
{
    return (double)(A.x - v[1].x) * (B.y - v[1].y) > (double)(B.x - v[1].x) * (A.y - v[1].y);
	
}

void graham()
{
    int S[DIM], top = 0;
    S[++top] = 1;
    S[++top] = 2;

    for (int i = 3; i <= n; ++i)
    {
        while (directie(v[S[top - 1]], v[S[top]], v[i]) <= 0 && top >= 2 ) //stanga
            --top;
        S[++top] = i;
    }
    FILE *f = fopen("infasuratoare.out", "w");
    fprintf (f, "%d\n", top);
    for (int i = 1; i <= top; ++i)
        fprintf(f, "%lf %lf\n", v[S[i]].x, v[S[i]].y);

}

int main()
{
    FILE *f = fopen("infasuratoare.in", "r");
    fscanf(f, "%d", &n);
    first.x = 1<<30, first.y = 1<<30;
	int ibun;
    for (int i = 1; i <= n; ++i)
    {
        fscanf(f, "%lf%lf", &v[i].x, &v[i].y);

        if (v[i].x < first.x)
            first.x = v[i].x, first.y = v[i].y, ibun = i;
        else
            if (v[i].x == first.x)
                if (v[i].y < first.y)
                    first.y = v[i].y, ibun = i;
    }
    fclose(f);
	swap(v[1], v[ibun]);
	for (int i = 1; i <= n; ++i)
		printf ("%lf %lf\n", v[i].x, v[i].y);
	printf ("\n");
    sort(v + 2, v + n + 1, fcmp);
	for (int i = 1; i <= n; ++i)
		printf ("%lf %lf\n", v[i].x, v[i].y);
	
    graham();
    return 0;
}