Cod sursa(job #859320)

Utilizator goguGogu Marian gogu Data 20 ianuarie 2013 09:00:44
Problema Oypara Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <ctime>
#include <algorithm>
#define MaxN 102300
 
using namespace std;
 
struct Point {
   double x, y;
};
 
struct Seg {
   Point p1, p2;
} seg[MaxN];
 
int N;
 
int main() {
   freopen("taie.in", "rb", stdin);
   freopen("taie.out", "wb", stdout);
 
   scanf("%d", &N);
   for (int i = 0; i < N; i++) {
      scanf("%lf %lf %lf", &seg[i].p1.x, &seg[i].p1.y, &seg[i].p2.y);
      seg[i].p2.x = seg[i].p1.x;
   }
    
   Point p1 = seg[0].p1;
   Point p2 = seg[1].p2;
 
   for (int iter = 0; iter < 9999; iter++) {
      double a = p2.y - p1.y;
      double b = p1.x - p2.x;
      double c = -(p1.x * p2.y - p1.y * p2.x);
      bool haveSol = true;
  
      for (int i = 0; i < N; i++) {
         swap(seg[i], seg[i + rand() % (N - i)]);
         double sgn1 = a * seg[i].p1.x  + b * seg[i].p1.y + c;
         double sgn2 = a * seg[i].p2.x  + b * seg[i].p2.y + c;
         if (sgn1 * sgn2 > 1e-8 && abs(sgn1) > 1e-8 && abs(sgn2) > 1e-8) {
            haveSol = false;
            p1 = p2;
            if (abs(sgn1) < abs(sgn2)) {
               p2 = seg[i].p1;
            } else {
               p2 = seg[i].p2;
            }
            break;
         }
      }
 
      if (haveSol) {
         printf("%.8f %.8f %.8f %.8f\n", p1.x, p1.y, p2.x, p2.y);
         return 0;
      }
   }
 
   printf("-1\n");
   return 0;
}