fork download
copy 
  1. #include<iostream>
  2. #include<math.h>
  3. #include<stdio.h>
  4. #include<vector>
  5. #include<iomanip>
  6.  
  7. #define rep(i,n) for( int i = 0 ; i < n ; i++ )
  8. #define FOR(i,b,c) for(int i = b ; i < c ; i++ )
  9. #define x first
  10. #define y second
  11. #define eps 1e-9
  12. #define MAXD 2
  13. #define eps 1e-9
  14. #define pi acos(-1.0)
  15. using namespace std ;
  16. struct Vec {
  17.     int d;
  18.     double val[MAXD];
  19.     Vec() {
  20.         d=2;
  21.     }
  22.     Vec( double a , double b ) {
  23.         val[0] = a ;
  24.         val[1] = b ;
  25.         d = 2 ;
  26.     }
  27.     Vec add ( Vec b ) {
  28.         Vec res;
  29.         FOR(i,0,d) res.val[i] = val[i] + b.val[i];
  30.         return res;
  31.     }
  32.     Vec sub ( Vec b ) {
  33.         Vec res;
  34.         FOR(i,0,d) res.val[i] = val[i] - b.val[i];
  35.         return res;
  36.     }
  37.     Vec mul ( double t ) {
  38.         Vec res;
  39.         FOR(i,0,d)res.val[i] = val[i] * t;
  40.         return res;
  41.     }
  42.     Vec div ( double t ) {
  43.         Vec res;
  44.         FOR(i,0,d) res.val[i] = val[i] / t;
  45.         return res;
  46.     }
  47.     Vec perp2D() {
  48.         Vec res = (*this);
  49.         swap ( res.val[0], res.val[1] );
  50.         res.val[0] *= -1;
  51.         return res;
  52.     }
  53.     double dot ( Vec v ) {
  54.         double res = 0;
  55.         d = 2 ;
  56.         for ( int i = 0; i < d; i++ ) res += val[i] * v.val[i];
  57.         return res;
  58.     }
  59.     double length () {
  60.         return sqrt ( this->dot( *this ) );
  61.     }
  62.     Vec unitVec () {
  63.         return (*this).div ( length() );
  64.     }
  65.     double angleBetween ( Vec b ) {
  66.         double res = dot( b ) / ( length() * b.length() );
  67.         if ( res > 1 ) res = 1;
  68.         if ( res < -1 ) res = -1;
  69.         return acos (res);
  70.     }
  71.     double polarAngle2D() {
  72.         double res = atan2 ( val[1], val[0] );
  73.         if ( res + eps < 0 ) res += 2 * pi;
  74.         return res;
  75.     }
  76.  
  77.     double cross2D ( Vec v ) {
  78.         return val[0]*v.val[1] - val[1]*v.val[0];
  79.     }
  80. };
  81.  
  82. struct Line {
  83.     Vec a, b;
  84.     Line() {}
  85.     Line( Vec x, Vec y ) {
  86.         a = x;
  87.         b = y.sub ( x );
  88.     }
  89.     double length() {
  90.         return b.length();
  91.     }
  92.     Vec atPos ( double t ) {
  93.         return a.add ( b.mul ( t ) );
  94.     }
  95.     bool overlapParallel ( Line l ) {
  96.         double p, q, r, s;
  97.         if ( b.val[0] == 0 ) {
  98.             p = a.val[1];
  99.             q = atPos(1).val[1];
  100.             r = l.a.val[1];
  101.             s = l.atPos ( 1 ).val[1];
  102.             if ( min ( r, s ) > max ( p, q ) ) return false;
  103.             if ( max ( r, s ) < min ( p, q ) ) return false;
  104.             return true;
  105.         } else {
  106.             p = a.val[0];
  107.             q = atPos(1).val[0];
  108.             r = l.a.val[0];
  109.             s = l.atPos ( 1 ).val[0];
  110.             if ( min ( r, s ) > max ( p, q ) ) return false;
  111.             if ( max ( r, s ) < min ( p, q ) ) return false;
  112.             return true;
  113.         }
  114.     }
  115.     char LineAndLineIntersection2D ( Line l, double &t, double &s ) {
  116.         if ( b.cross2D ( l.b) == 0 ) {
  117.             if ( l.a.sub(a).cross2D(l.b) == 0 ) {
  118.                 if ( overlapParallel ( l ) ) return 'o';
  119.                 else return 'p';
  120.             } else return 'd';
  121.         }
  122.         Vec w = a.sub ( l.a );
  123.         Vec p = l.b.perp2D(), z = b.perp2D();
  124.         t = -(w.dot(p))/p.dot(b);
  125.         s = w.dot(z)/z.dot(l.b);
  126.         return 'i';
  127.     }
  128. };
  129. vector< Vec > V ;
  130. int main() {
  131. #ifdef kryptonyte
  132.     freopen("in.txt","r",stdin ) ;
  133. #endif
  134.     int n ;
  135.     scanf("%d",&n) ;
  136.     vector<Vec> V ;
  137.     for( int i = 0 ; i < n ; i++ ) {
  138.         double x , y ;
  139.         scanf("%lf%lf",&x,&y) ;
  140.         Vec tmp = Vec(x,y);
  141.         V.push_back( tmp ) ;
  142.     }
  143.     int query ;
  144.     scanf("%d",&query ) ;
  145.     int ans = 0 ;
  146.     bool f = 0 ;
  147.     while( query-- ) {
  148.         int n1,n2,n3,n4 ;
  149.         scanf("%d%d%d%d",&n1,&n2,&n3,&n4) ;
  150.         if( !f ) {
  151.             n1-- ,n2--,n3--,n4-- ;
  152.             Line L1 = Line( V[n1] , V[n2] ) ;
  153.             Line L2 = Line( V[n3] , V[n4] ) ;
  154.             double t , s ;
  155.             L1.LineAndLineIntersection2D(L2,t,s) ;
  156.             Vec pt = L1.atPos(t) ;
  157.             if( fabs(pt.val[0]-0) < eps && fabs(pt.val[1]-0) < eps ) {
  158.                 f = 1 ;
  159.             }
  160.             ans ++ ;
  161.             V.push_back(pt) ;
  162.         }
  163.     }
  164.     if( f )cout << ans << "\n" ;
  165.     else cout << 0 << "\n" ;
  166.     return 0 ;
  167. }
Runtime error #stdin #stdout 0s 3100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2jMgAj
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!