fork download 
  1. #include <fstream>
  2. #include <iostream>
  3. #include <queue>
  4. #include <cmath>
  5. using namespace std;
  6.  
  7. #define F cin
  8. #define G cout
  9.  
  10. //ifstream F("p.in");
  11. //ofstream G("p.out");
  12.  
  13. /**
  14.  
  15. In loc sa ne plimbam cu nava printre obstacole , vom mari obstacolele si nava va deveni
  16. punctiforma. Acum pentru oricare 2 obstacole care se intersecteaza o sa trasam o muchie
  17. intre ele. O sa rezulte un graf planar si un punct initial.
  18.  
  19. Ca sa vedem daca punctul initial se afla in interiorul unui poligon trebuie sa determinam
  20. un ciclu care sa inconjoare punctul. Daca mergem pe un astfel de ciclu un sens trigonometric
  21. unghiul cu care mergem va creste constant. Astfel o sa facem un Bellman-Ford pe graf in care
  22. o sa cautam un ciclu negativ. Muchiile grafului vor fi unghiul facut de o latura fata de punctul
  23. de referinta.
  24.  
  25. */
  26.  
  27. const int Nmax = 310;
  28. const double EPS = 1e-10;
  29.  
  30. struct point
  31. {
  32.     double x,y;
  33. };
  34.  
  35. point operator - ( point a, point b )
  36. {
  37.     point c;
  38.     c.x = a.x - b.x;
  39.     c.y = a.y - b.y;
  40.     return c;
  41. }
  42.  
  43. point points[Nmax];
  44. double range[Nmax],act[Nmax];
  45. double angle[Nmax][Nmax];
  46. bool mark[Nmax][Nmax];
  47. int N,in[Nmax],times[Nmax];
  48. queue<int> Q;
  49.  
  50. int sign(double x)
  51. {
  52.     return x < -EPS ? -1 : x > EPS;
  53. }
  54.  
  55. double cross(point a,point b)
  56. {
  57.     return a.x * b.y - a.y * b.x;
  58. }
  59.  
  60. double dot(point a,point b)
  61. {
  62.     return a.x * b.x + a.y * b.y;
  63. }
  64.  
  65. double ang(point a,point b)
  66. {
  67.     return atan2( cross(a,b) , dot(a,b) );
  68. }
  69.  
  70. double sqr(double x)
  71. {
  72.     return x*x;
  73. }
  74.  
  75. double dist(point a,point b)
  76. {
  77.     return sqrt( sqr(a.x-b.x) + sqr(a.y-b.y) );
  78. }
  79.  
  80. void build_graph()
  81. {
  82.     for (int i=0;i<N;++i)
  83.         for (int j=0;j<N;++j)
  84.             if ( i != j )
  85.                 if ( sign( range[i] + range[j] + range[N] * 2.0 - dist(points[i],points[j]) ) == 1 )
  86.                 {
  87.                     mark[i][j] = 1;
  88.                     angle[i][j] = ang(points[i]-points[N],points[j]-points[N]);
  89.                 }
  90. }
  91.  
  92. int main()
  93. {
  94.     F>>N;
  95.     for (int i=0;i<=N;++i)
  96.     {
  97.         F>>points[i].x>>points[i].y;
  98.         F>>range[i];
  99.     }
  100.     build_graph();
  101.     for (int i=0;i<N;++i)
  102.     {
  103.         Q.push( i );
  104.         in[i] = 1;
  105.         act[i] = 0.0;
  106.     }
  107.     while ( Q.size() )
  108.     {
  109.         int i = Q.front();
  110.         Q.pop(), in[i] = 0;
  111.         for (int j=0;j<N;++j)
  112.             if ( mark[i][j] && sign( act[i] + angle[i][j] - act[j] ) < 0 )
  113.             {
  114.                 act[j] = act[i] + angle[i][j];
  115.                 if ( in[j] == 0 ) Q.push( j ), in[j] = 1;
  116.                 if ( ++times[j] > N )
  117.                 {
  118.                     G<<"NO\n";
  119.                     return 0;
  120.                 }
  121.             }
  122.     }
  123.     G<<"YES\n";
  124. }
  125.  
Success #stdin #stdout 0s 4336KB
comments (?)
stdin 
Standard input is empty
stdout 
YES
https://ideone.com/uH2SUt
language:
C++ (gcc 8.3)
created:
13 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!