Pagini recente » Cod sursa (job #1692068) | Cod sursa (job #3136288) | Cod sursa (job #2010262) | Cod sursa (job #840640) | Cod sursa (job #454969)
Cod sursa(job #454969)
#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.0001) 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;
}