Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <vector>
- #include <cmath>
- #include <set>
- #include <fstream>
- #include <cstring>
- #include <string>
- #include <algorithm>
- #include <map>
- #include <queue>
- #include <iterator>
- #include <iomanip>
- #include <bitset>
- #include <complex>
- #include <unordered_set>
- #include <unordered_map>
- using namespace std;
- #define sqr(x) ((x)*1ll*(x))
- #define cbr(x) ((x)*1ll*(x)*(x))
- //#define max(a, b) (((a)<(b))? (b):(a))
- //#define min(a, b) (((a)<(b))? (a):(b))
- #define all(a) a.begin(), a.end()
- #define _sp system("pause");
- #define _ok cout << "ok\n";
- #define _ln cout << "------------------------------------------------\n";
- #define FI(a, n) for(int i=a;i<n;i++)
- #define FJ(a, n) for(int j=a;j<n;j++)
- #define REP(a, b, c) for(int (c) = (a); (c) < (b); (c)++)
- #define rep(a, b, c) for(int (c) = (a); (c) < (b); (c)++)
- #define per(b, a, c) for(int (c) = (b); (c) >= (a); (c)--)
- #define ll long long
- #define ull unsigned long long
- #define uint unsigned int
- #define itn int
- #define pii pair<int, int>
- #define pll pair<ll, ll>
- #define pdd pair<double, double>
- #define mp(a, b) make_pair((a), (b))
- #define pb(a) push_back((a))
- /*
- #define x first
- #define y second
- #define x1 sasimathx1
- #define y1 sasimathy1
- #define prev etomoiprev
- #define left moilleft
- #define rank fsdfgmdsgd
- #define checkbit(n, b) (((n) >> (b)) & 1)
- #define setbit(n, b) ((n) | (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
- #define removebit(n, b) ((n) & ~(static_cast<std::decay<decltype(n)>::type>(1) << (b)))
- #define flipbit(n, b) ((n) ^ (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
- inline int countBits(uint v) { v = v - ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); return((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; }
- inline int countBits(ull v) { uint t = v >> 32; uint p = (v & ((1ULL << 32) - 1)); return countBits(t) + countBits(p); }
- inline int countBits(ll v) { return countBits((ull)v); }
- inline int countBits(int v) { return countBits((uint)v); }
- inline bool isPowerOfTwo(int x) { return (x != 0 && (x&(x - 1)) == 0); }
- inline ll mulmod(ll x, ll n, ll _mod) { ll res = 0; while (n) { if (n & 1)res = (res + x) % _mod; x = (x + x) % _mod; n >>= 1; }return res; }
- inline ll powmod(ll x, ll n, ll _mod) { ll res = 1; while (n) { if (n & 1)res = (res*x) % _mod; x = (x*x) % _mod; n >>= 1; }return res; }
- inline ll gcd(ll a, ll b) { ll t; while (b) { a = a % b; t = a; a = b; b = t; }return a; }
- inline int gcd(int a, int b) { int t; while (b) { a = a % b; t = a; a = b; b = t; }return a; }
- inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
- inline ll gcd(ll a, ll b, ll c) { return gcd(gcd(a, b), c); }
- inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
- // Fast IO ********************************************************************************************************
- const int __BS = 4096;
- static char __bur[__BS + 16], *__er = __bur + __BS, *__ir = __er;
- template<class T = int> T readInt() {
- auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
- c(); while (*__ir && (*__ir < '0' || *__ir > '9') && *__ir != '-') ++__ir; c();
- bool m = false; if (*__ir == '-') ++__ir, c(), m = true;
- T r = 0; while (*__ir >= '0' && *__ir <= '9') r = r * 10 + *__ir - '0', ++__ir, c();
- ++__ir; return m ? -r : r;
- }
- string readString() {
- auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
- string r; c(); while (*__ir && isspace(*__ir)) ++__ir, c();
- while (!isspace(*__ir)) r.push_back(*__ir), ++__ir, c();
- ++__ir; return r;
- }
- char readChar() {
- auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
- c(); while (*__ir && isspace(*__ir)) ++__ir, c(); return *__ir++;
- }
- static char __buw[__BS + 20], *__iw = __buw, *__ew = __buw + __BS;
- template<class T>
- void writeInt(T x, char endc = '\n') {
- if (x < 0) *__iw++ = '-', x = -x; if (x == 0) *__iw++ = '0';
- char* s = __iw;
- while (x) { T t = x / 10; char c = x - 10 * t + '0'; *__iw++ = c; x = t; }
- char* f = __iw - 1; while (s < f) swap(*s, *f), ++s, --f;
- if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw;
- if (endc) { *__iw++ = endc; }
- }
- template<class T>
- void writeStr(const T& str) {
- int i = 0; while (str[i]) { *__iw++ = str[i++]; if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw; }
- }
- struct __FL__ { ~__FL__() { if (__iw != __buw) cout.write(__buw, __iw - __buw); } };
- static __FL__ __flushVar__;
- // Print STL
- #define TT1 template<class T>
- #define TT1T2 template<class T1, class T2>
- #define TT1T2T3 template<class T1, class T2, class T3>
- TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
- TT1 ostream& operator << (ostream& os, const vector<T>& v) { bool f = 1; os << "["; for (auto& i : v) { if (!f)os << ", "; os << i; f = 0; }return os << "]"; }
- template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v) { bool f = 1; os << "["; for (auto& i : v) { if (!f)os << ", "; os << i; f = 0; }return os << "]"; }
- TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v) { bool f = 1; os << "["; for (auto& i : v) { if (!f)os << ", "; os << i; f = 0; }return os << "]"; }
- TT1T2 ostream& operator << (ostream& os, const multiset<T1, T2>&v) { bool f = 1; os << "["; for (auto& i : v) { if (!f)os << ", "; os << i; f = 0; }return os << "]"; }
- TT1T2T3 ostream& operator << (ostream& os, const map<T1, T2, T3>&v) { bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
- TT1T2 ostream& operator << (ostream& os, const multimap<T1, T2>&v) { bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
- TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2>v) { bool f = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!f) os << ", "; f = 0; os << x; } return os << "]"; }
- //DBG
- template<typename T, typename T2> void printarr(T a[], T2 sz, T2 beg = 0) { for (T2 i = beg; i < sz; i++) cout << a[i] << " "; cout << endl; }
- #define DBG(a) cout<<#a<<"="<<(a)<<"\n"
- #define DBG2(a,b) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
- #define DBG3(a,b,c) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
- #define DBG4(a,b,c,d) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
- //Files
- #define FILE_MODE(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
- */
- //Constants
- #define PI 3.1415926535897932
- #define INF 1011111111
- #define LLINF 1000111000111000111LL
- #define eps 1e-9
- //-------------------------------------------------
- #define rect vector<pair<pt, pt>>
- #define side pair<pt, pt>;
- struct pt {
- ll x, y;
- };
- inline int det(int a, int b, int c, int d) {
- return a*d - b-c;
- }
- inline bool isBetween(int a, int b, double c) {
- return min(a, b) <= c + eps && c <= max(a, b) + eps;
- }
- inline bool privateHasIntersention (int a, int b, int c, int d) {
- if (a > b) {
- swap(a, b);
- }
- if (c > d) {
- swap(c, d);
- }
- return max(a, c) <= max(b, d);
- }
- bool hasIntersection(pt a, pt b, pt c, pt d) {
- int A1 = a.y - b.y, B1 = b.x - a.x, C1 = -A1*a.x - B1*a.y;
- int A2 = c.y - d.y, B2 = d.x - c.x, C2 = -A2*c.x - B2*c.y;
- int s = det(A1, B1, A2, B2);
- if (s != 0) {
- double x = det(C1, B1, C2, B2) * 1. / s;
- double y = det(A1, C1, A2, C2) * 1. / s;
- return isBetween(a.x, b.x, x)
- && isBetween(a.y, b.y, y)
- && isBetween(c.x, d.x, x)
- && isBetween(c.y, d.y, y);
- }
- else {
- return det(A1, C1, A2, C2) == 0
- && det(B1, C1, B2, C2) == 0
- && privateHasIntersention(a.x, b.x, c.x, d.x)
- && privateHasIntersention(a.y, b.y, c.y, d.y);
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int RECTS;
- cin >> RECTS;
- vector<vector<pair<pt, pt>>> rects;
- vector<pt> rectsMaxPts;
- vector<pt> rectsMinPts;
- rep(0, RECTS, rectNumber) {
- int SIDES;
- cin >> SIDES;
- ll minX = LLINF;
- ll minY = LLINF;
- ll maxX = -LLINF;
- ll maxY = -LLINF;
- vector<pair<pt, pt>> sides;
- rep(0, SIDES, sideNumber) {
- ll x, y;
- cin >> x >> y;
- if (sides.size() == 0) {
- ll x2, y2;
- cin >> x2 >> y2;
- sides.push_back(mp({x, y}, {x2, y2}));
- minX = min(minX, min(x, x2));
- minY = min(minY, min(y, y2));
- maxX = max(maxX, max(x, x2));
- maxY = max(maxY, max(y, y2));
- sideNumber++;
- }
- else {
- ll x1 = sides[sides.size() - 1].second.x;
- ll y1 = sides[sides.size() - 1].second.y;
- sides.push_back(mp(pt(x1, y1), pt(x, y)));
- if (sideNumber == SIDES - 1) {
- ll x0 = sides[0].first.x;
- ll y0 = sides[0].first.y;
- sides.push_back(mp(pt(x, y), pt(x0, y0)));
- }
- }
- }
- rects.push_back(sides);
- rectsMinPts.push_back(pt(minX, minY));
- rectsMaxPts.push_back(pt(maxX, maxY));
- }
- ll POINTS;
- cin >> points;
- rep(0, POINTS, pointNumber) {
- ll xp, yp;
- cin >> xp >> yp;
- ll hitCount = 0;
- rep(0, rects.size(), rectNumber) {
- int intersections = 0;
- rect r = rects[rectNumber];
- rep(0, r.size(), sideNumber) {
- side s = r[sideNumber];
- if (hasIntersection({xp, yp}, {xp, rectsMaxPts[rectNumber].y}, s.first, s.second)) intersections++;
- if (hasIntersection({xp, yp}, {xp, rectsMinPts[rectNumber].y}, s.first, s.second)) intersections++;
- if (hasIntersection({xp, yp}, {rectsMaxPts[rectNumber].x, yp}, s.first, s.second)) intersections++;
- if (hasIntersection({xp, yp}, {rectsMinPts[rectNumber].x, yp}, s.first, s.second)) intersections++;
- }
- if (intersections >= 4) {
- hitCount++;
- }
- }
- cout << hitCount << endl;
- }
- return 0;
- }
- // #define N 10010
- //pair<int, pii> p[N];
- //ll dst(pii a, pii b) {
- // return sqr(a.x - b.x) + sqr(a.y - b.y);
- //}
- /*
- int main()
- {
- //ios::sync_with_stdio(0);
- //cin.tie(0);
- vector<vector<pair<pll, pair<double, double>>>> rects;
- vector<pair<pll, pll>> minMaxXYForRects;
- ll N; // number of rects
- cin >> N;
- DBG(N);
- rep (0, N, i) { // rects
- DBG(i);
- vector<pair<pll, pair<double, double>>> rect; //
- ll rectMaxX = -INF, rectMaxY = -INF, rectMinX = INF, rectMinY = INF;
- ll M; // number of rect points
- cin >> M;
- DBG(M);
- ll rectOriginX, rectOriginY;
- rep(0, M, j) { // rect points
- DBG(j);
- ll x, y;
- cin >> x >> y;
- DBG2(x, y);
- if (rect.empty()) { // first point
- rectOriginX = x;
- rectOriginY = y;
- ll x2, y2;
- cin >> x2 >> y2;
- double k = (x - x2) != 0 ? ((double)(y - y2) / (double)(x - x2)) : LLINF;
- double b = (x - x2) != 0 ? y2 - (double)x2 * k : x;
- DBG2(k, b);
- pll origin = mp(x2, y2);
- pair<double, double> consts = mp(k, b);
- pair<pll, pair<double, double>> line = mp(origin, consts);
- rect.push_back(line);
- j++;
- rectMinX = min(rectMinX, min(x, x2));
- rectMinY = min(rectMinY, min(y, y2));
- rectMaxX = max(rectMaxX, max(x, x2));
- rectMaxY = max(rectMaxY, max(y, y2));
- }
- else {
- ll x1 = rect[rect.size() - 1].first.first;
- ll y1 = rect[rect.size() - 1].first.second;
- double k = (x1 - x) != 0 ? ((double)(y1 - y) / (double)(x1 - x)) : LLINF;
- double b = (x1 - x) != 0 ? y - (double)x * k : x;
- DBG2(k, b);
- pll origin = mp(x, y);
- pair<double, double> consts = mp(k, b);
- pair<pll, pair<double, double>> line = mp(origin, consts);
- rect.push_back(line);
- rectMinX = min(rectMinX, min(x, x1));
- rectMinY = min(rectMinY, min(y, y1));
- rectMaxX = max(rectMaxX, max(x, x1));
- rectMaxY = max(rectMaxY, max(y, y1));
- if (j == M - 1) {
- ll x2 = rectOriginX;
- ll y2 = rectOriginY;
- double k2 = (x - x2) != 0 ? ((double)(y - y2) / (double)(x - x2)) : LLINF;
- double b2 = (x - x2) != 0 ? y2 - (double)x2 * k : x;
- DBG2(k2, b2);
- pll origin2 = mp(x2, y2);
- pair<double, double> consts2 = mp(k2, b2);
- pair<pll, pair<double, double>> line2 = mp(origin2, consts2);
- rect.push_back(line2);
- }
- }
- }
- rects.push_back(rect);
- minMaxXYForRects.push_back(mp(mp(rectMinX, rectMinY), mp(rectMaxX, rectMaxY)));
- }
- ll Q;
- cin >> Q;
- rep(0, Q, i) {
- ll xp, yp;
- cin >> xp >> yp;
- int hitCount = 0;
- rep(0, rects.size(), j) {
- ll rectMinX = minMaxXYForRects[j].first.first;
- ll rectMinY = minMaxXYForRects[j].first.second;
- ll rectMaxX = minMaxXYForRects[j].second.first;
- ll rectMaxY = minMaxXYForRects[j].second.second;
- if (xp < rectMinX || xp > rectMaxX || yp < rectMinX || yp > rectMaxY) {
- continue;
- }
- bool isInsideRect = false;
- vector<pair<pll, pair<double, double>>> rect = rects[j];
- int crossCount = 0;
- for (double p = xp; p >= rectMinX; p -= 0.01) {
- bool isCrossFound = false;
- rep(0, rect.size(), sideIndex) {
- pair<pll, pair<double, double>> side;
- ll sideX = side.first.first;
- ll sideY = side.first.second;
- ll sideK = side.second.first;
- ll sideB = side.second.second;
- double k = (xp - sideX) != 0 ? (double)(yp - sideY) / (double)(xp - sideX) : LLINF;
- double b = (xp - sideX) != 0 ? sideY - (double)sideX * k : xp;
- if (k == sideK && b == sideB) {
- isCrossFound = true;
- break;
- }
- }
- if (isCrossFound) {
- crossCount++;
- break;
- }
- }
- for (double p = xp; p <= rectMaxX; p += 0.01) {
- bool isCrossFound = false;
- rep(0, rect.size(), sideIndex) {
- pair<pll, pair<double, double>> side;
- ll sideX = side.first.first;
- ll sideY = side.first.second;
- ll sideK = side.second.first;
- ll sideB = side.second.second;
- double k = (xp - sideX) != 0 ? (double)(yp - sideY) / (double)(xp - sideX) : LLINF;
- double b = (xp - sideX) != 0 ? sideY - (double)sideX * k : xp;
- if (k == sideK && b == sideB) {
- isCrossFound = true;
- break;
- }
- }
- if (isCrossFound) {
- crossCount++;
- break;
- }
- }
- for (double p = yp; p >= rectMinY; p -= 0.01) {
- bool isCrossFound = false;
- rep(0, rect.size(), sideIndex) {
- pair<pll, pair<double, double>> side;
- ll sideX = side.first.first;
- ll sideY = side.first.second;
- ll sideK = side.second.first;
- ll sideB = side.second.second;
- double k = (xp - sideX) != 0 ? (double)(yp - sideY) / (double)(xp - sideX) : LLINF;
- double b = (xp - sideX) != 0 ? sideY - (double)sideX * k : xp;
- if (k == sideK && b == sideB) {
- isCrossFound = true;
- break;
- }
- }
- if (isCrossFound) {
- crossCount++;
- break;
- }
- }
- for (double p = yp; p >= rectMaxY; p += 0.01) {
- bool isCrossFound = false;
- rep(0, rect.size(), sideIndex) {
- pair<pll, pair<double, double>> side;
- ll sideX = side.first.first;
- ll sideY = side.first.second;
- ll sideK = side.second.first;
- ll sideB = side.second.second;
- double k = (xp - sideX) != 0 ? (double)(yp - sideY) / (double)(xp - sideX) : LLINF;
- double b = (xp - sideX) != 0 ? sideY - (double)sideX * k : xp;
- if (k == sideK && b == sideB) {
- isCrossFound = true;
- break;
- }
- }
- if (isCrossFound) {
- crossCount++;
- break;
- }
- }
- isInsideRect = crossCount >= 4;
- if (isInsideRect) {
- hitCount++;
- }
- }
- cout << hitCount << endl;
- }
- return 0;
- }*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement