fork(3) download 
  1. #include <iostream> 
  2. #include <cmath>
  3. typedef double long dl;
  4. using namespace std;
  5. const double E = 1e-6;
  6. bool on_edge(dl x, dl y, dl x1, dl y1, dl x2, dl y2) {
  7.     bool res = false;
  8.     if (fabs(x2 - x1) < E) {
  9.         if (fabs(x - x1) < E && y > min(y1, y2) - E && y - E < max(y1, y2)) res = true;
  10.     } else {
  11.         x -= x1;
  12.         y -= y1;
  13.         x2 -= x1;
  14.         y2 -= y1;
  15.         if (x - E < max(x1, x2) && x > min(x1, x2) - E && fabs(x2 * y - y2 * x) < E) {
  16.             res = true;
  17.         }
  18.     }
  19.     return res;
  20. }
  21. bool cross(dl x0, dl y0, dl x1, dl y1, dl x2, dl y2){
  22.     return (y1 < y0 && y2 > y0 - E || y2 < y0 && y1 > y0 - E) && (y0 * (x1 - x2) + y1 * x2 - x1 * y2) / (y1 - y2) < x0;
  23. }
  24. int main() {
  25.     ios::sync_with_stdio(0);
  26.     cin.tie(0);
  27.     cout.tie(0);
  28.     dl x0, y0, xs, ys, xt, yt, xi, yi;
  29.     int n;
  30.     cin >> n >> x0 >> y0;
  31.     cin >> xs >> ys;
  32.     xt = xs;
  33.     yt = ys;
  34.     bool par_am = false;
  35.     bool on_side = false;
  36.     n--;
  37.     while (n-- && !on_side) {
  38.         cin >> xi >> yi;
  39.         if (on_edge(x0, y0, xt, yt, xi, yi)) {
  40.             on_side = true;
  41.         }
  42.         if (cross(x0, y0, xt, yt, xi, yi)) {
  43.             par_am = !par_am;
  44.         }
  45.         xt = xi;
  46.         yt = yi;
  47.     }
  48.     if (on_edge(x0, y0, xt, yt, xs, ys)) {
  49.         on_side = true;
  50.     }
  51.     if (cross(x0, y0, xt, yt, xs, ys)) {
  52.         par_am = !par_am;
  53.     }
  54.     cout << (par_am || on_side ? "YES" : "NO");
  55.     return 0;
  56. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
6 1 1
0 0
0 2
1 4
2 2
2 0
1 3
stdout 
NO
https://ideone.com/ZwZgxE
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!