Cod sursa(job #402110)

Utilizator cristiprgPrigoana Cristian cristiprg Data 23 februarie 2010 15:14:23
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.19 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
#define DIM 100005
const int INF = 1<<30;
struct point
{
	int x, y;
	friend bool operator == (point A, point B)
	{
        if (A.x == B.x && A.y == B.y)
            return true;
        return false;
    }
} v[DIM];

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

int mod (int a)
{
    return a<0?-a:a;
}

double mod(double a)
{
    return a<0?-1:a;
}

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

int n;

void read()
{
	FILE *f = fopen("rubarba.in", "r");
	fscanf(f, "%d", &n);
	point first;
	int ibun = -1;
	first.x = 1<<30, first.y = 1<<30;
	for (int i = 1; i <= n; ++i)
	{
		fscanf(f, "%d%d", &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]);
}

int directie(point A, point B, point C)
{
	int d = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);

	if (d == 0)//inainte
		return 0;
	if (d < 0)
		return -1;//dreapta
	return 1;//stanga
}

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)
			--top;
		S[++top] = i;
	}
	n = top;
	for (int i = 1; i <= n; ++i)
		v[i] = v[S[i]];


}

double dist(point  P1, point P2 , point P) //distanta de la dreapta (P1 P2) la P
{
	return ((P1.y - P2.y) * P.x + (P2.x - P1.x) * P.y + P2.y * P1.x - P1.y * P2.x ) / sqrt((P1.y - P2.y) * (P1.y - P2.y) + (P2.x - P1.x) * (P2.x - P1.x));
}
double dist(point P1, point P2)
{
    return sqrt((P1.x - P2.x) * (P1.x - P2.x) + (P1.y - P2.y) * (P1.y - P2.y));
}

point cel_mai_din_stanga_al_dreptei(point P1, point P2)
{
	int ibun;

	double Dist, dist_min = -1;

	for (int i = 1; i <= n; ++i)
	{
        Dist = dist(P1, P2, v[i]);

        if (dist_min < Dist && Dist >= 0)
        {

            if (v[i] == P1 && v[ibun] == P2 || v[ibun] == P1 && v[i] == P2)
            {

                if (v[i].y < v[ibun].y)
                    dist_min = Dist, ibun = i;
            }
            else
                printf ("ba\n"), fflush(stdout),dist_min = Dist, ibun = i ;
        }
	}


	return v[ibun];

}


point cel_mai_din_dreapta_al_dreptei(point P1, point P2, point Q)
{
    int ibun;
	double Dist, dist_min = (double)INF;

	for (int i = 1; i <= n; ++i)
	{
        Dist = dist(P1, P2, v[i]);

        if (dist_min > Dist && Dist <= 0)
           if (!(v[i] == Q))
                dist_min = Dist, ibun = i;
	}


	return v[ibun];
}



void solve()
{
	double dmax = -1, d, A, Amin = (double)INF;
    int pbun = -1;
	point Pstanga, Pdreapta;

	for (int i = 1; i < n; ++i) //pt toate dreptele
	{

		for (int j = 1; j <= n; ++j)
			if (i != j && (i+1) != j) //pt toate celalalte puncte
			{

				d = dist(v[i], v[i+1], v[j]);
				if (d > dmax)
					dmax = d, pbun = j;

			}
        fflush(stdout);
		Pstanga = cel_mai_din_stanga_al_dreptei(v[i], v[i+1]);
        Pdreapta= cel_mai_din_dreapta_al_dreptei(v[i], v[i+1], Pstanga);
        if (Pstanga == Pdreapta)
            printf ("CUR!\n");

        //aflu dist de la Pdreapta la dreapta ( v[i], Pstanga)
        if (!(v[i] == Pstanga) && !(v[i] == Pdreapta))
            d = dist(v[i], Pstanga, Pdreapta);
        else
            if (v[i] == Pdreapta)
                d = dist(v[i], Pstanga);
            else
                d = dist(v[i], Pdreapta);
        printf ("(%d %d) (%d %d) (%d %d) (%d %d) d = %lf\n", v[i].x, v[i].y, v[pbun].x, v[pbun].y, Pstanga.x, Pstanga.y, Pdreapta.x, Pdreapta.y, d);
        A = d * dmax;
        printf ("A = %lf * %lf = %lf\n",d, dmax, A);
        if (A < Amin)
            Amin = A;


	}
	FILE *f = fopen("rubarba.out", "w");
	fprintf (f, "%.2lf", Amin);
	fclose(f);
}

int main()
{
	read();
	sort(v + 2, v + n + 1, cmpf);
	graham();
//	solve();
    point ba = cel_mai_din_stanga_al_dreptei(v[1], v[2]);
    printf ("%d %d\n", ba.x, ba.y);


	return 0;
}