Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
- #pragma GCC optimize 03
- #pragma GCC optimize("unroll-loops")
- #include <iostream>
- #include <iomanip>
- #include <algorithm>
- #include <iterator>
- #include <cmath>
- #include <ctime>
- #include <vector>
- #include <deque>
- #include <queue>
- #include <set>
- #include <map>
- #include <stack>
- #include <string>
- #include <random>
- #include <numeric>
- #include <unordered_set>
- typedef long long ll;
- typedef long double lb;
- #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- #define file_in freopen("input.txt", "r", stdin);
- #define file_in_out freopen("cutting.in", "r", stdin); freopen("cutting.out", "w", stdout);
- #define mp make_pair
- #define pll pair<lb, lb>
- #define all(x) (x).begin(), (x).end()
- #define fi first
- #define se second
- using namespace std;
- template<typename T>
- istream& operator>>(istream &in, vector<T> &v) {
- for (auto &it : v) {
- in >> it;
- }
- return in;
- }
- template<typename T>
- ostream& operator<<(ostream &out, vector<T> &v) {
- if (!v.empty()) {
- out << v.front();
- for (int i = 1; i < (int)v.size(); ++i) {
- out << " " << v[i];
- }
- }
- return out;
- }
- lb x3, y3, x4, y4;
- lb dist(lb x1, lb y1, lb x2, lb y2) {
- return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
- }
- void func(lb x1, lb y1, lb x2, lb y2) {
- lb r = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) / sqrt(2);
- x2 -= x1; y2 -= y1;
- lb a = -2 * x2, b = -2 * y2;
- lb c = x2 * x2 + y2 * y2;
- lb x0 = -a * c / (a * a + b * b), y0 = -b * c / (a * a + b * b);
- lb d = r * r - c * c / (a * a + b * b);
- lb mult = sqrt(d / (a * a + b * b));
- x3 = x0 + b * mult;
- x4 = x0 - b * mult;
- y3 = y0 - a * mult;
- y4 = y0 + a * mult;
- x3 += x1; x4 += x1; y3 += y1; y4 += y1;
- }
- lb sqr(lb s1, lb s2, lb s3) {
- lb p = (s1 + s2 + s3) / 2;
- return sqrt(p * (p - s1) * (p - s2) * (p - s3));
- }
- bool check(lb x, lb y, lb x1, lb y1, lb x2, lb y2, lb x3, lb y3) {
- lb d1 = dist(x, y, x1, y1);
- lb d2 = dist(x, y, x2, y2);
- lb d3 = dist(x, y, x3, y3);
- lb d4 = dist(x1, y1, x2, y2);
- lb d5 = dist(x2, y2, x3, y3);
- lb d6 = dist(x1, y1, x3, y3);
- return (abs(sqr(d4, d5, d6) - (sqr(d1, d2, d4) + sqr(d2, d3, d5) + sqr(d1, d3, d5))) <= 1e-8);
- }
- int main() {
- fast
- // file_in
- // file_in_out
- int n, q;
- cin >> n >> q;
- vector<pll> coords(n);
- for (auto &[x, y] : coords) cin >> x >> y;
- int type;
- lb x1, y1, x2, y2;
- while (q--) {
- cin >> type >> x1 >> y1 >> x2 >> y2;
- if (type == 1) {
- lb a = y1 - y2;
- lb b = x2 - x1;
- lb c = -a * x1 - b * y1;
- bool is = false;
- for (auto [x, y] : coords) {
- if ((a * x + b * y + c <= 0) == (a * (x1 + y2 - y1) + b * (y1 + x1 - x2) + c <= 0)) {
- is = true;
- break;
- }
- }
- if (is) {
- cout << "Yes" << "\n";
- } else {
- cout << "No" << "\n";
- }
- } else {
- func(x1, y1, x2, y2);
- bool is = false;
- for (auto [x, y] : coords) {
- if (check(x, y, x1, y1, x2, y2, x3, y3) || check(x, y, x1, y1, x2, y2, x4, y4)) {
- is = true;
- }
- }
- if (is) {
- cout << "Yes" << "\n";
- } else {
- cout << "No" << "\n";
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement