Advertisement
MathQ_

Untitled

Dec 20th, 2020
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.59 KB | None | 0 0
  1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  2. #pragma GCC optimize 03
  3. #pragma GCC optimize("unroll-loops")
  4.  
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <algorithm>
  8. #include <iterator>
  9. #include <cmath>
  10. #include <ctime>
  11. #include <vector>
  12. #include <deque>
  13. #include <queue>
  14. #include <set>
  15. #include <map>
  16. #include <stack>
  17. #include <string>
  18. #include <random>
  19. #include <numeric>
  20. #include <unordered_set>
  21.  
  22. typedef long long ll;
  23. typedef long double lb;
  24.  
  25. #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  26. #define file_in freopen("input.txt", "r", stdin);
  27. #define file_in_out freopen("cutting.in", "r", stdin); freopen("cutting.out", "w", stdout);
  28. #define mp make_pair
  29. #define pll pair<lb, lb>
  30. #define all(x) (x).begin(), (x).end()
  31. #define fi first
  32. #define se second
  33.  
  34. using namespace std;
  35.  
  36. template<typename T>
  37. istream& operator>>(istream &in, vector<T> &v) {
  38.     for (auto &it : v) {
  39.         in >> it;
  40.     }
  41.     return in;
  42. }
  43.  
  44. template<typename T>
  45. ostream& operator<<(ostream &out, vector<T> &v) {
  46.     if (!v.empty()) {
  47.         out << v.front();
  48.         for (int i = 1; i < (int)v.size(); ++i) {
  49.             out << " " << v[i];
  50.         }
  51.     }
  52.     return out;
  53. }
  54.  
  55. lb x3, y3, x4, y4;
  56.  
  57. lb dist(lb x1, lb y1, lb x2, lb y2) {
  58.     return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  59. }
  60.  
  61. void func(lb x1, lb y1, lb x2, lb y2) {
  62.     lb r = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) / sqrt(2);
  63.  
  64.     x2 -= x1; y2 -= y1;
  65.    
  66.     lb a = -2 * x2, b = -2 * y2;
  67.     lb c = x2 * x2 + y2 * y2;
  68.     lb x0 = -a * c / (a * a + b * b), y0 = -b * c / (a * a + b * b);
  69.     lb d = r * r - c * c / (a * a + b * b);
  70.     lb mult = sqrt(d / (a * a + b * b));
  71.  
  72.     x3 = x0 + b * mult;
  73.     x4 = x0 - b * mult;
  74.     y3 = y0 - a * mult;
  75.     y4 = y0 + a * mult;
  76.    
  77.     x3 += x1; x4 += x1; y3 += y1; y4 += y1;
  78. }
  79.  
  80. lb sqr(lb s1, lb s2, lb s3) {
  81.     lb p = (s1 + s2 + s3) / 2;
  82.     return sqrt(p * (p - s1) * (p - s2) * (p - s3));
  83. }
  84.  
  85. bool check(lb x, lb y, lb x1, lb y1, lb x2, lb y2, lb x3, lb y3) {
  86.     lb d1 = dist(x, y, x1, y1);
  87.     lb d2 = dist(x, y, x2, y2);
  88.     lb d3 = dist(x, y, x3, y3);
  89.  
  90.     lb d4 = dist(x1, y1, x2, y2);
  91.     lb d5 = dist(x2, y2, x3, y3);
  92.     lb d6 = dist(x1, y1, x3, y3);
  93.     return (abs(sqr(d4, d5, d6) - (sqr(d1, d2, d4) + sqr(d2, d3, d5) + sqr(d1, d3, d5))) <= 1e-8);  
  94. }
  95.  
  96. int main() {
  97.     fast
  98. //  file_in
  99. //  file_in_out
  100.  
  101.     int n, q;
  102.     cin >> n >> q;
  103.     vector<pll> coords(n);
  104.     for (auto &[x, y] : coords) cin >> x >> y;
  105.     int type;
  106.     lb x1, y1, x2, y2;
  107.     while (q--) {
  108.         cin >> type >> x1 >> y1 >> x2 >> y2;
  109.         if (type == 1) {
  110.             lb a = y1 - y2;
  111.             lb b = x2 - x1;
  112.             lb c = -a * x1 - b * y1;
  113.             bool is = false;
  114.             for (auto [x, y] : coords) {
  115.                 if ((a * x + b * y + c <= 0) == (a * (x1 + y2 - y1) + b * (y1 + x1 - x2) + c <= 0)) {
  116.                     is = true;
  117.                     break;
  118.                 }
  119.             }
  120.             if (is) {
  121.                 cout << "Yes" << "\n";
  122.             } else {
  123.                 cout << "No" << "\n";
  124.             }
  125.         } else {
  126.             func(x1, y1, x2, y2);
  127.             bool is = false;
  128.             for (auto [x, y] : coords) {
  129.                 if (check(x, y, x1, y1, x2, y2, x3, y3) || check(x, y, x1, y1, x2, y2, x4, y4)) {
  130.                     is = true;
  131.                 }
  132.             }
  133.             if (is) {
  134.                 cout << "Yes" << "\n";
  135.             } else {
  136.                 cout << "No" << "\n";
  137.             }
  138.         }
  139.     }
  140.     return 0;
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement