Cod sursa(job #454971)

Utilizator savimSerban Andrei Stan savim Data 12 mai 2010 21:15:03
Problema Oypara Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 100010
#define MAX_COR 1000000000
#define double long double

int n;
struct segment {
	int x, y1, y2;
} A[MAX_N];

inline int cmp(const segment &A, const segment &B) {
	return A.x < B.x;
}

int verif(double CorX, double CorY) {
	struct dreapta {
    	int x, y;
	} up, down;

	up.x = A[1].x; up.y = A[1].y2;
	down.x = A[1].x; down.y = A[1].y1;

	for (int i = 2; i <= n; i++) {
    	if ((A[i].y2 - CorY) * (up.x - CorX) < (up.y - CorY) * (A[i].x - CorX)) {
			up.x = A[i].x;
			up.y = A[i].y2;
		}

		//verific daca up < down
		if ((up.y - CorY) * (down.x - CorX) < (down.y - CorY) * (up.x - CorX))
			return -1;

        if ((A[i].y1 - CorY) * (down.x - CorX) > (down.y - CorY) * (A[i].x - CorX)) {
            down.x = A[i].x;
            down.y = A[i].y1;
        }

		//verific daca down > up
        if ((down.y - CorY) * (up.x - CorX) > (up.y - CorY) * (down.x - CorX))
            return 1;
	}

	return 0;
}

inline int egal(double A, double B) {
	double diff = A - B;
	if (diff < 0) diff = B - A;

	if (diff < 0.1) return 1;
	return 0;                
}

void get_sol(double CorX, double CorY) {
    struct dreapta {
        int x, y;
    } down; //imi trebuia unghiul de jos

    down.x = A[1].x; down.y = A[1].y1;
    for (int i = 2; i <= n; i++)
        if ((A[i].y1 - CorY) * (down.x - CorX) > (down.y - CorY) * (A[i].x - CorX)) {
            down.x = A[i].x;
            down.y = A[i].y1;
        }

	int nr_afis = 0;
	for (int i = 1; i <= n; i++) { //afisez capetele segmentelor ce au aceeasi tangenta cu (down.x, down.y)
    	if (nr_afis == 2) 
			break;
		if (egal((A[i].y1 - CorY) * (down.x - CorX), (down.y - CorY) * (A[i].x - CorX))) {
			if (nr_afis == 1) 
				printf(" "); 
			printf("%d %d", A[i].x, A[i].y1);
			nr_afis++;
		}

		if (nr_afis == 2)
			break;
        if (egal((A[i].y2 - CorY) * (down.x - CorX), (down.y - CorY) * (A[i].x - CorX))) {
            if (nr_afis == 1) 
                printf(" ");
            printf("%d %d", A[i].x, A[i].y2);
            nr_afis++;
        }
	}

	printf("\n");
}

void solve() { //trebuie sa gasesc punctul coordonata y cea mai mica; punctul (0,y) sigur va intersecta doua capete de segment
	double jos = -MAX_COR, sus = MAX_COR, sol;
	for (int nr_pasi = 1; nr_pasi <= 70; nr_pasi++) {
    	sol = 1.0 * (jos + sus) / 2;

		//vreau sa vad daca pot trage o dreapta care are ca punct de start (0, mid)
		int answer = verif(0, sol);
		
		if (answer == 0 || answer == 1) //unghiul de jos a depasit pe cel de sus sau am solutie
        	sus = sol;
		else //unghiul de sus a ajuns mai mic fata cel de jos
			jos = sol; 
	}

	get_sol(0, sol);
}

int main() {
	freopen("oypara.in", "r", stdin);
	freopen("oypara.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d %d %d", &A[i].x, &A[i].y1, &A[i].y2);

	sort(A + 1, A + n + 1, cmp);

	solve();

	return 0;
}