fork 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
stdin
6 1 1
0 0
0 2
1 4
2 2
2 0
1 3
stdout
NO