robredz.cpp

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cmath>

#undef DEBUG

#define IFILE   "robredz.dat"
#define OFILE   "robredz.rez"
#define MAXROCKS 30000
#define M_DIF  1.0e-10
#define MAX(x,y)    (((x)>(y))?(x):(y))
#define MIN(x,y)    (((x)<(y))?(x):(y))

#ifdef DEBUG
#define COMPSTR  (i == 25)
#endif

using namespace std;

struct s_kli { long frX,toX,frY,toY,frN,toN,initI, live, incl; double frR,toR; } kli[MAXROCKS*2];
struct s_seg { long iN,iN0,iN1,iBS; double iR0, iR1; } seg[8];

long double round(long double r){
     return ( r > 0.0) ? floor(r+0.5) : ceil(r-0.5);
     }

int compare (const void * a, const void * b){
     const s_kli *ia = (const s_kli *)a;
     const s_kli *ib = (const s_kli *)b;
     if( (*ia).frN != (*ib).frN ) return ((*ia).frN - (*ib).frN);
     return 0;
     }

int main(int argc, char *argv[])
{

long N,R,X,Y;
int addR = 0,tmpIDX;
long frX,toX,tmpX,prX,frY,toY,tmpY,prY;
int i,j,k,tos,frs,swapQ;
long double frR,toR,tmpR,prR;
long double d_frsk,d_tosk;

ifstream ifs (IFILE);
if( ifs.is_open() ){
  ifs >> N >> R >> X >> Y;
  seg[0].iN = Y;   seg[0].iBS = X;   seg[0].iN0 = 1;               seg[0].iN1 = Y;       seg[0].iR0 = -M_PI;      seg[0].iR1 = atan2(-(long double)Y,-(long double)X);
  seg[1].iN = X;   seg[1].iBS = Y;   seg[1].iN0 = seg[0].iN1+1;    seg[1].iN1 = X+Y;     seg[1].iR0 = seg[0].iR1; seg[1].iR1 = -M_PI/2;
  seg[2].iN = N-X; seg[2].iBS = Y;   seg[2].iN0 = seg[1].iN1+1;    seg[2].iN1 = Y+N;     seg[2].iR0 = seg[1].iR1; seg[2].iR1 = atan2(-(long double)Y,(long double)(N-X));
  seg[3].iN = Y;   seg[3].iBS = N-X; seg[3].iN0 = seg[2].iN1+1;    seg[3].iN1 = 2*Y+N;   seg[3].iR0 = seg[2].iR1; seg[3].iR1 = 0.0;
  seg[4].iN = N-Y; seg[4].iBS = N-X; seg[4].iN0 = seg[3].iN1+1;    seg[4].iN1 = 2*N+Y;   seg[4].iR0 = seg[3].iR1; seg[4].iR1 = atan2((long double)(N-Y),(long double)(N-X));
  seg[5].iN = N-X; seg[5].iBS = N-Y; seg[5].iN0 = seg[4].iN1+1;    seg[5].iN1 = 3*N+Y-X; seg[5].iR0 = seg[4].iR1; seg[5].iR1 = M_PI/2.0;
  seg[6].iN = X;   seg[6].iBS = N-Y; seg[6].iN0 = seg[5].iN1+1;    seg[6].iN1 = 3*N+Y;   seg[6].iR0 = seg[5].iR1; seg[6].iR1 = atan2((long double)(N-Y),-(long double)X);
  seg[7].iN = N-Y; seg[7].iBS = X;   seg[7].iN0 = seg[6].iN1+1;    seg[7].iN1 = 4*N;     seg[7].iR0 = seg[6].iR1; seg[7].iR1 = M_PI;


  for( i = 0; i < R; i++){
    ifs >> k;
    ifs >> frX >> frY;
    toX = frX; toY = frY; prX = frX; prY = frY;
    frR = toR = prR = atan2((long double)(frY-Y),(long double)(frX-X));
    swapQ = 0;
    for( j = 1; j < k; j++ ){
        ifs >> tmpX >> tmpY;
        tmpR = atan2((long double)(tmpY-Y),(long double)(tmpX-X));
        if( fabs(prR-tmpR) > M_PI & (!swapQ) ){
            swapQ = 1;
            if( prR > tmpR ) { toR = tmpR; toX = tmpX; toY = tmpY; }
            else { frR = tmpR; frX = tmpX; frY = tmpY; }
        } else if (swapQ) {
             if( (tmpR < frR) && (tmpR > 0.0 ) )  { frR = tmpR; frX = tmpX; frY = tmpY; }
             else if ( (tmpR > toR) && (tmpR < 0.0) ) { toR = tmpR; toX = tmpX; toY = tmpY; }
        } else {
            if( tmpR < frR ) { frR = tmpR; frX = tmpX; frY = tmpY; }
            else if (tmpR > toR ) { toR = tmpR; toX = tmpX; toY = tmpY; }
        }
        prX = tmpX; prY = tmpY; prR = tmpR;
    }
    kli[i].frX = frX; kli[i].frY = frY; kli[i].frR = frR;
    kli[i].toX = toX; kli[i].toY = toY; kli[i].toR = toR;
    kli[i].initI = i;
    kli[i].live = 1;

    frs = -1; tos = -1; // from segment, to segment

    for( j = 0; j < 8; j++ ) {
        if( (frR >= seg[j].iR0) && (frR <= seg[j].iR1) ) frs = j;
        if( (toR >= seg[j].iR0) && (toR <= seg[j].iR1) ) tos = j;
        }

// Apstrādājam no punktu
    if( frY == Y ){
        if ( frX < X ) frs = 7; else frs = 3;
        kli[i].frN=seg[frs].iN1;
    } else if( frX == X ){
        if ( frY < Y ) frs = 1; else frs = 5;
        kli[i].frN=seg[frs].iN1;
    } else if( frs % 2 == 1 ){  // OK
        d_frsk = fabs((long double)(seg[frs].iBS)*tan(seg[frs].iR1-kli[i].frR));
        kli[i].frN = seg[frs].iN1 - (long)floor(d_frsk+M_DIF);
    } else if( frs % 2 == 0 ){ // OK
        d_frsk = fabs((long double)(seg[frs].iBS)*tan(kli[i].frR-seg[frs].iR0));
        kli[i].frN = seg[frs].iN0 - 1 + (long)ceil(d_frsk-M_DIF);
    }


// Apstrādājam lidz punktu
    if( toY == Y ){
        if ( toX < X ) tos = 7; else tos = 3;
        kli[i].toN=seg[tos].iN1;
    } else if( toX == X ){
        if ( toY < Y ) tos = 1; else tos = 5;
        kli[i].toN=seg[tos].iN1;
    } else if( tos % 2 == 1 ){ // OK
        d_tosk = fabs((long double)(seg[tos].iBS)*tan(seg[tos].iR1-kli[i].toR));
        kli[i].toN = seg[tos].iN1 - 1 - (long)floor(d_tosk-M_DIF);
    } else if( tos % 2 == 0 ){ // OK
        d_tosk = fabs((long double)(seg[tos].iBS)*tan(kli[i].toR-seg[tos].iR0));
        kli[i].toN = seg[tos].iN0 - 1 + (long)floor(d_tosk+M_DIF);
    }

    if( (frR-toR)>0.0 ) {
        tmpIDX = R + (++addR) - 1;
        kli[tmpIDX].frN = 1;
        kli[tmpIDX].toN = kli[i].toN;
        kli[tmpIDX].live = 1;
        kli[tmpIDX].initI = tmpIDX;
        kli[i].toN = 4*N;

    }

}
}
ifs.close();

R += addR;
qsort(kli,R,sizeof(struct s_kli),compare);

int     stabi = 0;
/*---------------------------*/
/* Sakam sektoru apvienosanu */


long frS,frT,toS,toT;

i = 0;
while( i < R ){
     j = i ;
     while( ++j < R ){
          if( !kli[j].live ) continue;
          frT = kli[i].frN; toT = kli[i].toN; frS = kli[j].frN; toS = kli[j].toN;
          if( (frS >= frT) && ( toS <= toT )) { kli[j].live = 0; kli[j].incl = kli[i].initI;
          } else if ( ( frS > toT+1 ) || (toS < frT -1) ) { i = j-1; break;
          } else {
                 kli[j].live = 0; kli[j].incl = kli[i].initI;
                 if( frT > frS )kli[i].frN = frS;
                 if( toT < toS ) kli[i].toN = toS;
                 }
     }
     if( j == R ) break;
     ++i;
}


/*---------------------------------------*/
/* Skaitam neredzamos stabiņus             */

tmpX = 0;
for( i = 0; i < R; i++ ){
     if( kli[i].live ) tmpX += (kli[i].toN - kli[i].frN + 1);
     }

stabi = 4*N-tmpX;

ofstream ofs (OFILE);
if( ofs.is_open() ){
    ofs << stabi << endl;
    ofs.close();
    }
    return 0;
}