Cod sursa(job #525695)

Utilizator vladiiIonescu Vlad vladii Data 25 ianuarie 2011 22:14:46
Problema Oypara Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 kb
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define maxn 100010
#define LL long long

int N, nriPS, nriPJ;
int top, S[maxn];

struct Polygon {
    int x, y;
} PS[maxn], PJ[maxn], iPS[maxn], iPJ[maxn];

int cmp(Polygon a, Polygon b) {
    return a.x < b.x;
}

LL produs(Polygon P1, Polygon P2, Polygon P3) {
    return (LL)P2.x*P3.y - (LL)P2.x*P1.y - (LL)P1.x*P3.y + (LL)P1.x*P1.y -
           (LL)P3.x*P2.y + (LL)P3.x*P1.y + (LL)P1.x*P2.y - (LL)P1.x*P1.y;
}

void PUSH(int val) {
    top ++;
    S[top] = val;
}

void POP() {
     top --;
}

int intersect(int indj, int inds) {
   int x1 = iPJ[indj].x, y1 = iPJ[indj].y;
   int x2 = iPS[inds].x, y2 = iPS[inds].y;

   LL A = (y2 - y1);
   LL B = -(x2 - x1);
   LL C = (LL)x1 * y1 - (LL)x2 * y1;

   int check1 = inds + 1;
   if(check1 > nriPS) check1 = 1;

   int check2 = inds - 1;
   if(check2 < 1) check2 = nriPS;

   LL semn1 = (LL)A * iPS[check1].x + (LL)B * iPS[check1].y - C;
   LL semn2 = (LL)A * iPS[check2].x + (LL)B * iPS[check2].y - C;

   if((semn1 < 0 && semn2 > 0) || (semn1 > 0 && semn2 < 0)) {
        return 1; //linia intersecteaza poligonul de sus
   }

   check1 = indj + 1;
   if(check1 > nriPJ) check1 = 1;

   check2 = indj - 1;
   if(check2 < 1) check2 = nriPJ;

   semn1 = (LL)A * iPJ[check1].x + (LL)B * iPJ[check1].y - C;
   semn2 = (LL)A * iPJ[check2].x + (LL)B * iPJ[check2].y - C;

   if((semn1 < 0 && semn2 > 0) || (semn1 > 0 && semn2 < 0)) {
        return 2; //linia intersecteaza poligonul de jos
   }

   return 0; //linia nu intersecteaza poligonul
}

int main() {
    FILE *f1=fopen("oypara.in", "r"), *f2=fopen("oypara.out", "w");
    int i, j, y1, y2;

    fscanf(f1, "%d\n", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d %d %d\n", &j, &y1, &y2);
         if(y1 > y2) swap(y1, y2);

         PJ[i].x = j, PJ[i].y = y1;
         PS[i].x = j, PS[i].y = y2;
    }

    sort(PJ+1, PJ+N+1, cmp);
    sort(PS+1, PS+N+1, cmp);

    //partea superioara a infasuratorii convexe
    //a poligonului de jos (PJ)
    PUSH(N); PUSH(N-1);
    for(i=N-2; i>=1; i--) {
         LL o = produs(PJ[ S[top-1] ], PJ[ S[top] ], PJ[i]);
         while(top > 1 && o <= 0) {
              POP();
              o = produs(PJ[ S[top-1] ], PJ[ S[top] ], PJ[i]);
         }
         PUSH(i);
    }
    for(i=1; i<=top; i++) {
         nriPJ ++;
         iPJ[nriPJ] = PJ[ S[i] ];
         //cout<<iPJ[nriPJ].x<<" "<<iPJ[nriPJ].y<<endl;
    }
    //cout<<endl;

    //partea inferioara a infasuratorii conevexe
    //a poligonului de sus (PS)
    top = 0;
    PUSH(1); PUSH(2);
    for(i=3; i<=N; i++) {
         LL o = produs(PS[ S[top-1] ], PS[ S[top] ], PS[i]);
         while(top > 1 && o <= 0) {
              POP();
              o = produs(PS[ S[top-1] ], PS[ S[top] ], PS[i]);
         }
         PUSH(i);
    }
    for(i=1; i<=top; i++) {
         nriPS ++;
         iPS[nriPS] = PS[ S[i] ];
         //cout<<iPS[nriPS].x<<" "<<iPS[nriPS].y<<endl;
    }
    //cout<<endl;

    //gasirea celor 2 puncte
    int indj = nriPJ, inds = nriPS;
    while(indj >= 1 && inds >= 1) {
         //verific cele doua perechi
         int rez = intersect(indj, inds);
         if(rez == 0) {
              fprintf(f2, "%d %d %d %d\n", iPJ[indj].x, iPJ[indj].y, iPS[inds].x, iPS[inds].y);
              fclose(f1); fclose(f2);
              return 0;
         }
         else if(rez == 1) {
              //intersecteaza poligonul de sus
              inds --;
         }
         else if(rez == 2) {
              //intersecteaza poligonul de jos
              indj --;
         }
    }

    fprintf(f2, "%d\n", -1); //no solution
    fclose(f1); fclose(f2);
    return 0;
}