Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 18.11 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <vector>
  5. #include <cmath>
  6. #include <set>
  7. #include <fstream>
  8. #include <cstring>
  9. #include <string>
  10. #include <algorithm>
  11. #include <map>
  12. #include <queue>
  13. #include <iterator>
  14. #include <iomanip>
  15. #include <bitset>
  16. #include <complex>
  17. #include <unordered_set>
  18. #include <unordered_map>
  19. using namespace std;
  20.  
  21. #define sqr(x) ((x)*1ll*(x))
  22. #define cbr(x) ((x)*1ll*(x)*(x))
  23. //#define max(a, b) (((a)<(b))? (b):(a))
  24. //#define min(a, b) (((a)<(b))? (a):(b))
  25. #define all(a) a.begin(), a.end()
  26.  
  27. #define _sp system("pause");
  28. #define _ok cout << "ok\n";
  29. #define _ln cout << "------------------------------------------------\n";
  30. #define FI(a, n) for(int i=a;i<n;i++)
  31. #define FJ(a, n) for(int j=a;j<n;j++)
  32. #define REP(a, b, c) for(int (c) = (a); (c) < (b); (c)++)
  33. #define rep(a, b, c) for(int (c) = (a); (c) < (b); (c)++)
  34. #define per(b, a, c) for(int (c) = (b); (c) >= (a); (c)--)
  35.  
  36. #define ll long long
  37. #define ull unsigned long long
  38. #define uint unsigned int
  39. #define itn int
  40. #define pii pair<int, int>
  41. #define pll pair<ll, ll>
  42. #define pdd pair<double, double>
  43. #define mp(a, b) make_pair((a), (b))
  44. #define pb(a) push_back((a))
  45.  
  46. /*
  47. #define x first
  48. #define y second
  49.  
  50. #define x1 sasimathx1
  51. #define y1 sasimathy1
  52. #define prev etomoiprev
  53. #define left moilleft
  54. #define rank fsdfgmdsgd
  55.  
  56. #define checkbit(n, b) (((n) >> (b)) & 1)
  57. #define setbit(n, b) ((n) | (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
  58. #define removebit(n, b) ((n) & ~(static_cast<std::decay<decltype(n)>::type>(1) << (b)))
  59. #define flipbit(n, b) ((n) ^ (static_cast<std::decay<decltype(n)>::type>(1) << (b)))
  60. inline int countBits(uint v) { v = v - ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); return((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; }
  61. inline int countBits(ull v) { uint t = v >> 32; uint p = (v & ((1ULL << 32) - 1)); return countBits(t) + countBits(p); }
  62. inline int countBits(ll v) { return countBits((ull)v); }
  63. inline int countBits(int v) { return countBits((uint)v); }
  64. inline bool isPowerOfTwo(int x) { return (x != 0 && (x&(x - 1)) == 0); }
  65.  
  66. 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; }
  67. 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; }
  68. inline ll gcd(ll a, ll b) { ll t; while (b) { a = a % b; t = a; a = b; b = t; }return a; }
  69. inline int gcd(int a, int b) { int t; while (b) { a = a % b; t = a; a = b; b = t; }return a; }
  70. inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
  71. inline ll gcd(ll a, ll b, ll c) { return gcd(gcd(a, b), c); }
  72. inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
  73. // Fast IO ********************************************************************************************************
  74. const int __BS = 4096;
  75. static char __bur[__BS + 16], *__er = __bur + __BS, *__ir = __er;
  76. template<class T = int> T readInt() {
  77. auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
  78. c(); while (*__ir && (*__ir < '0' || *__ir > '9') && *__ir != '-') ++__ir; c();
  79. bool m = false; if (*__ir == '-') ++__ir, c(), m = true;
  80. T r = 0; while (*__ir >= '0' && *__ir <= '9') r = r * 10 + *__ir - '0', ++__ir, c();
  81. ++__ir; return m ? -r : r;
  82. }
  83. string readString() {
  84. auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
  85. string r; c(); while (*__ir && isspace(*__ir)) ++__ir, c();
  86. while (!isspace(*__ir)) r.push_back(*__ir), ++__ir, c();
  87. ++__ir; return r;
  88. }
  89. char readChar() {
  90. auto c = [&]() { if (__ir == __er) std::fill(__bur, __bur + __BS, 0), cin.read(__bur, __BS), __ir = __bur; };
  91. c(); while (*__ir && isspace(*__ir)) ++__ir, c(); return *__ir++;
  92. }
  93. static char __buw[__BS + 20], *__iw = __buw, *__ew = __buw + __BS;
  94. template<class T>
  95. void writeInt(T x, char endc = '\n') {
  96. if (x < 0) *__iw++ = '-', x = -x; if (x == 0) *__iw++ = '0';
  97. char* s = __iw;
  98. while (x) { T t = x / 10; char c = x - 10 * t + '0'; *__iw++ = c; x = t; }
  99. char* f = __iw - 1; while (s < f) swap(*s, *f), ++s, --f;
  100. if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw;
  101. if (endc) { *__iw++ = endc; }
  102. }
  103. template<class T>
  104. void writeStr(const T& str) {
  105. int i = 0; while (str[i]) { *__iw++ = str[i++]; if (__iw > __ew) cout.write(__buw, __iw - __buw), __iw = __buw; }
  106. }
  107. struct __FL__ { ~__FL__() { if (__iw != __buw) cout.write(__buw, __iw - __buw); } };
  108. static __FL__ __flushVar__;
  109.  
  110. // Print STL
  111. #define TT1 template<class T>
  112. #define TT1T2 template<class T1, class T2>
  113. #define TT1T2T3 template<class T1, class T2, class T3>
  114. TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
  115. 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 << "]"; }
  116. 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 << "]"; }
  117. 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 << "]"; }
  118. 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 << "]"; }
  119. 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 << "]"; }
  120. 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 << "]"; }
  121. 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 << "]"; }
  122.  
  123. //DBG
  124. 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; }
  125. #define DBG(a) cout<<#a<<"="<<(a)<<"\n"
  126. #define DBG2(a,b) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
  127. #define DBG3(a,b,c) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
  128. #define DBG4(a,b,c,d) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
  129.  
  130. //Files
  131. #define FILE_MODE(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
  132. */
  133. //Constants
  134. #define PI 3.1415926535897932
  135. #define INF 1011111111
  136. #define LLINF 1000111000111000111LL
  137. #define eps 1e-9
  138. //-------------------------------------------------
  139.  
  140. #define rect vector<pair<pt, pt>>
  141. #define side pair<pt, pt>;
  142.  
  143. struct pt {
  144. ll x, y;
  145. };
  146.  
  147. inline int det(int a, int b, int c, int d) {
  148. return a*d - b-c;
  149. }
  150.  
  151. inline bool isBetween(int a, int b, double c) {
  152. return min(a, b) <= c + eps && c <= max(a, b) + eps;
  153. }
  154.  
  155. inline bool privateHasIntersention (int a, int b, int c, int d) {
  156. if (a > b) {
  157. swap(a, b);
  158. }
  159. if (c > d) {
  160. swap(c, d);
  161. }
  162. return max(a, c) <= max(b, d);
  163. }
  164.  
  165. bool hasIntersection(pt a, pt b, pt c, pt d) {
  166. int A1 = a.y - b.y, B1 = b.x - a.x, C1 = -A1*a.x - B1*a.y;
  167. int A2 = c.y - d.y, B2 = d.x - c.x, C2 = -A2*c.x - B2*c.y;
  168. int s = det(A1, B1, A2, B2);
  169.  
  170. if (s != 0) {
  171. double x = det(C1, B1, C2, B2) * 1. / s;
  172. double y = det(A1, C1, A2, C2) * 1. / s;
  173.  
  174. return isBetween(a.x, b.x, x)
  175. && isBetween(a.y, b.y, y)
  176. && isBetween(c.x, d.x, x)
  177. && isBetween(c.y, d.y, y);
  178. }
  179. else {
  180. return det(A1, C1, A2, C2) == 0
  181. && det(B1, C1, B2, C2) == 0
  182. && privateHasIntersention(a.x, b.x, c.x, d.x)
  183. && privateHasIntersention(a.y, b.y, c.y, d.y);
  184. }
  185. }
  186.  
  187. int main() {
  188. ios_base::sync_with_stdio(0);
  189. cin.tie(0);
  190.  
  191. int RECTS;
  192. cin >> RECTS;
  193.  
  194. vector<vector<pair<pt, pt>>> rects;
  195. vector<pt> rectsMaxPts;
  196. vector<pt> rectsMinPts;
  197.  
  198. rep(0, RECTS, rectNumber) {
  199. int SIDES;
  200. cin >> SIDES;
  201.  
  202. ll minX = LLINF;
  203. ll minY = LLINF;
  204. ll maxX = -LLINF;
  205. ll maxY = -LLINF;
  206.  
  207. vector<pair<pt, pt>> sides;
  208.  
  209. rep(0, SIDES, sideNumber) {
  210. ll x, y;
  211. cin >> x >> y;
  212.  
  213. if (sides.size() == 0) {
  214. ll x2, y2;
  215. cin >> x2 >> y2;
  216.  
  217. sides.push_back(mp({x, y}, {x2, y2}));
  218.  
  219. minX = min(minX, min(x, x2));
  220. minY = min(minY, min(y, y2));
  221. maxX = max(maxX, max(x, x2));
  222. maxY = max(maxY, max(y, y2));
  223.  
  224. sideNumber++;
  225. }
  226. else {
  227. ll x1 = sides[sides.size() - 1].second.x;
  228. ll y1 = sides[sides.size() - 1].second.y;
  229.  
  230. sides.push_back(mp(pt(x1, y1), pt(x, y)));
  231.  
  232. if (sideNumber == SIDES - 1) {
  233. ll x0 = sides[0].first.x;
  234. ll y0 = sides[0].first.y;
  235.  
  236. sides.push_back(mp(pt(x, y), pt(x0, y0)));
  237. }
  238. }
  239. }
  240.  
  241. rects.push_back(sides);
  242. rectsMinPts.push_back(pt(minX, minY));
  243. rectsMaxPts.push_back(pt(maxX, maxY));
  244. }
  245.  
  246. ll POINTS;
  247. cin >> points;
  248.  
  249. rep(0, POINTS, pointNumber) {
  250. ll xp, yp;
  251. cin >> xp >> yp;
  252.  
  253. ll hitCount = 0;
  254.  
  255. rep(0, rects.size(), rectNumber) {
  256. int intersections = 0;
  257.  
  258. rect r = rects[rectNumber];
  259.  
  260. rep(0, r.size(), sideNumber) {
  261. side s = r[sideNumber];
  262.  
  263. if (hasIntersection({xp, yp}, {xp, rectsMaxPts[rectNumber].y}, s.first, s.second)) intersections++;
  264. if (hasIntersection({xp, yp}, {xp, rectsMinPts[rectNumber].y}, s.first, s.second)) intersections++;
  265. if (hasIntersection({xp, yp}, {rectsMaxPts[rectNumber].x, yp}, s.first, s.second)) intersections++;
  266. if (hasIntersection({xp, yp}, {rectsMinPts[rectNumber].x, yp}, s.first, s.second)) intersections++;
  267. }
  268.  
  269. if (intersections >= 4) {
  270. hitCount++;
  271. }
  272. }
  273.  
  274. cout << hitCount << endl;
  275. }
  276.  
  277. return 0;
  278. }
  279. // #define N 10010
  280.  
  281. //pair<int, pii> p[N];
  282.  
  283. //ll dst(pii a, pii b) {
  284. // return sqr(a.x - b.x) + sqr(a.y - b.y);
  285. //}
  286. /*
  287.  
  288. int main()
  289. {
  290. //ios::sync_with_stdio(0);
  291. //cin.tie(0);
  292.  
  293. vector<vector<pair<pll, pair<double, double>>>> rects;
  294. vector<pair<pll, pll>> minMaxXYForRects;
  295.  
  296. ll N; // number of rects
  297. cin >> N;
  298. DBG(N);
  299. rep (0, N, i) { // rects
  300. DBG(i);
  301.  
  302. vector<pair<pll, pair<double, double>>> rect; //
  303. ll rectMaxX = -INF, rectMaxY = -INF, rectMinX = INF, rectMinY = INF;
  304.  
  305. ll M; // number of rect points
  306. cin >> M;
  307. DBG(M);
  308.  
  309. ll rectOriginX, rectOriginY;
  310.  
  311. rep(0, M, j) { // rect points
  312. DBG(j);
  313.  
  314. ll x, y;
  315. cin >> x >> y;
  316.  
  317. DBG2(x, y);
  318.  
  319. if (rect.empty()) { // first point
  320. rectOriginX = x;
  321. rectOriginY = y;
  322.  
  323. ll x2, y2;
  324. cin >> x2 >> y2;
  325.  
  326. double k = (x - x2) != 0 ? ((double)(y - y2) / (double)(x - x2)) : LLINF;
  327. double b = (x - x2) != 0 ? y2 - (double)x2 * k : x;
  328.  
  329. DBG2(k, b);
  330.  
  331. pll origin = mp(x2, y2);
  332. pair<double, double> consts = mp(k, b);
  333. pair<pll, pair<double, double>> line = mp(origin, consts);
  334.  
  335. rect.push_back(line);
  336. j++;
  337.  
  338. rectMinX = min(rectMinX, min(x, x2));
  339. rectMinY = min(rectMinY, min(y, y2));
  340. rectMaxX = max(rectMaxX, max(x, x2));
  341. rectMaxY = max(rectMaxY, max(y, y2));
  342. }
  343. else {
  344. ll x1 = rect[rect.size() - 1].first.first;
  345. ll y1 = rect[rect.size() - 1].first.second;
  346.  
  347. double k = (x1 - x) != 0 ? ((double)(y1 - y) / (double)(x1 - x)) : LLINF;
  348. double b = (x1 - x) != 0 ? y - (double)x * k : x;
  349.  
  350. DBG2(k, b);
  351.  
  352. pll origin = mp(x, y);
  353. pair<double, double> consts = mp(k, b);
  354. pair<pll, pair<double, double>> line = mp(origin, consts);
  355. rect.push_back(line);
  356.  
  357. rectMinX = min(rectMinX, min(x, x1));
  358. rectMinY = min(rectMinY, min(y, y1));
  359. rectMaxX = max(rectMaxX, max(x, x1));
  360. rectMaxY = max(rectMaxY, max(y, y1));
  361.  
  362. if (j == M - 1) {
  363. ll x2 = rectOriginX;
  364. ll y2 = rectOriginY;
  365.  
  366. double k2 = (x - x2) != 0 ? ((double)(y - y2) / (double)(x - x2)) : LLINF;
  367. double b2 = (x - x2) != 0 ? y2 - (double)x2 * k : x;
  368.  
  369. DBG2(k2, b2);
  370.  
  371. pll origin2 = mp(x2, y2);
  372. pair<double, double> consts2 = mp(k2, b2);
  373. pair<pll, pair<double, double>> line2 = mp(origin2, consts2);
  374. rect.push_back(line2);
  375. }
  376. }
  377. }
  378. rects.push_back(rect);
  379. minMaxXYForRects.push_back(mp(mp(rectMinX, rectMinY), mp(rectMaxX, rectMaxY)));
  380.  
  381. }
  382.  
  383. ll Q;
  384. cin >> Q;
  385.  
  386. rep(0, Q, i) {
  387. ll xp, yp;
  388. cin >> xp >> yp;
  389.  
  390. int hitCount = 0;
  391.  
  392. rep(0, rects.size(), j) {
  393. ll rectMinX = minMaxXYForRects[j].first.first;
  394. ll rectMinY = minMaxXYForRects[j].first.second;
  395. ll rectMaxX = minMaxXYForRects[j].second.first;
  396. ll rectMaxY = minMaxXYForRects[j].second.second;
  397.  
  398. if (xp < rectMinX || xp > rectMaxX || yp < rectMinX || yp > rectMaxY) {
  399. continue;
  400. }
  401.  
  402. bool isInsideRect = false;
  403.  
  404. vector<pair<pll, pair<double, double>>> rect = rects[j];
  405.  
  406. int crossCount = 0;
  407.  
  408. for (double p = xp; p >= rectMinX; p -= 0.01) {
  409. bool isCrossFound = false;
  410.  
  411. rep(0, rect.size(), sideIndex) {
  412. pair<pll, pair<double, double>> side;
  413. ll sideX = side.first.first;
  414. ll sideY = side.first.second;
  415. ll sideK = side.second.first;
  416. ll sideB = side.second.second;
  417.  
  418. double k = (xp - sideX) != 0 ? (double)(yp - sideY) / (double)(xp - sideX) : LLINF;
  419. double b = (xp - sideX) != 0 ? sideY - (double)sideX * k : xp;
  420.  
  421. if (k == sideK && b == sideB) {
  422. isCrossFound = true;
  423. break;
  424. }
  425. }
  426.  
  427. if (isCrossFound) {
  428. crossCount++;
  429. break;
  430. }
  431. }
  432.  
  433. for (double p = xp; p <= rectMaxX; p += 0.01) {
  434. bool isCrossFound = false;
  435.  
  436. rep(0, rect.size(), sideIndex) {
  437. pair<pll, pair<double, double>> side;
  438. ll sideX = side.first.first;
  439. ll sideY = side.first.second;
  440. ll sideK = side.second.first;
  441. ll sideB = side.second.second;
  442.  
  443. double k = (xp - sideX) != 0 ? (double)(yp - sideY) / (double)(xp - sideX) : LLINF;
  444. double b = (xp - sideX) != 0 ? sideY - (double)sideX * k : xp;
  445.  
  446. if (k == sideK && b == sideB) {
  447. isCrossFound = true;
  448. break;
  449. }
  450. }
  451.  
  452. if (isCrossFound) {
  453. crossCount++;
  454. break;
  455. }
  456. }
  457.  
  458. for (double p = yp; p >= rectMinY; p -= 0.01) {
  459. bool isCrossFound = false;
  460.  
  461. rep(0, rect.size(), sideIndex) {
  462. pair<pll, pair<double, double>> side;
  463. ll sideX = side.first.first;
  464. ll sideY = side.first.second;
  465. ll sideK = side.second.first;
  466. ll sideB = side.second.second;
  467.  
  468. double k = (xp - sideX) != 0 ? (double)(yp - sideY) / (double)(xp - sideX) : LLINF;
  469. double b = (xp - sideX) != 0 ? sideY - (double)sideX * k : xp;
  470.  
  471. if (k == sideK && b == sideB) {
  472. isCrossFound = true;
  473. break;
  474. }
  475. }
  476.  
  477. if (isCrossFound) {
  478. crossCount++;
  479. break;
  480. }
  481. }
  482.  
  483. for (double p = yp; p >= rectMaxY; p += 0.01) {
  484. bool isCrossFound = false;
  485.  
  486. rep(0, rect.size(), sideIndex) {
  487. pair<pll, pair<double, double>> side;
  488. ll sideX = side.first.first;
  489. ll sideY = side.first.second;
  490. ll sideK = side.second.first;
  491. ll sideB = side.second.second;
  492.  
  493. double k = (xp - sideX) != 0 ? (double)(yp - sideY) / (double)(xp - sideX) : LLINF;
  494. double b = (xp - sideX) != 0 ? sideY - (double)sideX * k : xp;
  495.  
  496. if (k == sideK && b == sideB) {
  497. isCrossFound = true;
  498. break;
  499. }
  500. }
  501.  
  502. if (isCrossFound) {
  503. crossCount++;
  504. break;
  505. }
  506. }
  507.  
  508. isInsideRect = crossCount >= 4;
  509.  
  510. if (isInsideRect) {
  511. hitCount++;
  512. }
  513. }
  514.  
  515. cout << hitCount << endl;
  516. }
  517.  
  518. return 0;
  519. }*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement