Guest User

Untitled

a guest
Aug 31st, 2015
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.95 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <string.h>
  5. #include <queue>
  6. #include <math.h>
  7. #include <cmath>
  8. #include <map>
  9. #include <set>
  10. #include <vector>
  11. #include <algorithm>
  12. #include <bitset>
  13. #include <list>
  14. #include <ctype.h>
  15. #include <cassert>
  16. #include <stack>
  17. #include <fstream>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20. #include <ctime>
  21. #include <functional>
  22. #include <ctime>
  23.  
  24. using namespace std;
  25.  
  26. #define snd second
  27. #define fst first
  28. #define mp make_pair
  29. #define ll long long
  30. #define ull unsigned long long
  31. #define ld long double
  32. #define pb push_back
  33. #define left _left
  34. #define right _right
  35.  
  36. const ld pi = 3.14159265359;
  37.  
  38. template<typename T>
  39. T abs(T x) {
  40.     return x > 0 ? x : -x;
  41. }
  42.  
  43. template<typename T>
  44. T sqr(T x) {
  45.     return x * x;
  46. }
  47.  
  48. template<typename T>
  49. void chmin(T &x, T y) {
  50.     x = min(x, y);
  51. }
  52.  
  53. template<typename T>
  54. void chmax(T &x, T y) {
  55.     x = max(x, y);
  56. }
  57.  
  58. template<typename U, typename V>
  59. ostream& operator << (ostream &s, const pair<U, V> &x) {
  60.     s << "(" << x.fst << ", " << x.snd << ")";
  61.     return s;
  62. }
  63.  
  64. template<typename U>
  65. ostream& operator << (ostream &s, const vector<U> &x) {
  66.     s << "[";
  67.     bool was = false;
  68.     for (auto it : x) {
  69.         if (was) {
  70.             s << ", ";
  71.         }
  72.         was = true;
  73.         s << it;
  74.     }
  75.     s << "]";
  76.     return s;
  77. }
  78.  
  79. //-----------------------------------------------------------------------------
  80.  
  81. const ld eps = 1e-9;
  82.  
  83. struct pt {
  84.     ll x, y;
  85.  
  86.     pt(ll _x = 0, ll _y = 0) {
  87.         x = _x, y = _y;
  88.     }
  89.  
  90.     pt operator + (const pt &o) const {
  91.         return pt(x + o.x, y + o.y);
  92.     }
  93.  
  94.     pt operator - (const pt &o) const {
  95.         return pt(x - o.x, y - o.y);
  96.     }
  97.  
  98.     ll operator ^ (const pt &o) const {
  99.         return x * o.y - y * o.x;
  100.     }
  101.  
  102.     ll operator % (const pt &o) const {
  103.         return x * o.x + y * o.y;
  104.     }
  105.  
  106.     ld len() {
  107.         return sqrt(sqr(x) + sqr(y));
  108.     }
  109.  
  110.     static pt read() {
  111.         ll x, y;
  112.         cin >> x >> y;
  113.         //x = rand() % 1000, y = rand() % 100;
  114.         return pt(x, y);
  115.     }
  116.  
  117.     bool operator < (const pt &o) const {
  118.         return mp(x, y) < mp(o.x, o.y);
  119.     }
  120. };
  121.  
  122. ll area(pt a, pt b, pt c) {
  123.     return abs((b - a) ^ (c - a));
  124. }
  125.  
  126. int brute(vector<pt> a, vector<pt> b) {
  127.     int ans = 0;
  128.  
  129.     for (auto u : a) {
  130.         for (auto v : a) {
  131.             for (auto w : a) {
  132.                 ll s = area(u, v, w);
  133.                 if (!s) {
  134.                     continue;
  135.                 }
  136.  
  137.                 bool bad = false;
  138.                 for (auto p : b) {
  139.                     bad |=
  140.                         area(u, v, p) + area(u, w, p) + area(v, w, p) == s &&
  141.                         area(u, v, p) && area(u, w, p) && area(v, w, p);
  142.                 }
  143.  
  144.                 if (!bad) {
  145.                     ans++;
  146.                 }
  147.             }
  148.         }
  149.     }
  150.  
  151.     assert(ans % 6 == 0);
  152.     return ans / 6;
  153. }
  154.  
  155. void gen() {
  156.     ofstream out("a.in");
  157.     int n = 500, m = 500;
  158.     out << n << " " << m << endl;
  159.     for (int i = 0; i < n; i++) {
  160.         int x = rand() % 1000, y = rand() % 1000;
  161.         out << x << " " << y << endl;
  162.     }
  163.  
  164.     for (int i = 0; i < m; i++) {
  165.         int x = rand() % 1000, y = rand() % 1000;
  166.         out << x << " " << y << endl;
  167.     }
  168.  
  169.     out.close();
  170. }
  171.  
  172.  
  173. int main() {
  174.     srand(time(NULL));
  175.  
  176.     retry:
  177.  
  178. #ifdef LOCAL
  179.     gen();
  180.     //cerr << 1 << endl;
  181.     freopen("a.in", "r", stdin);
  182. #else
  183.     //freopen("fract.in", "r", stdin);
  184.     //freopen("fract.out", "w", stdout);
  185. #endif
  186.  
  187.     vector<pt> a, b;
  188.     int n, m;
  189.     cin >> n >> m;
  190.     //n = 500, m = 500;
  191.  
  192.     for (int i = 0; i < n; i++) {
  193.         a.pb(pt::read());
  194.     }
  195.  
  196.     for (int i = 0; i < m; i++) {
  197.         b.pb(pt::read());
  198.     }
  199.  
  200.     int ans = 0;
  201.  
  202.     for (int i = 0; i < n; i++) {
  203.  
  204.         auto u = a[i];
  205.  
  206.         //cerr << i << endl;
  207.  
  208.         vector<pair<ld, pair<int, pt>>> c;
  209.         int qty = 1;
  210.         for (auto x : a) {
  211.             if (qty != i + 1) {
  212.                 ld ang = atan2(x.y - a[i].y, x.x - a[i].x);
  213.                 c.pb(mp(ang, mp(qty, x)));
  214.             }
  215.             qty++;
  216.         }
  217.  
  218.         for (auto x : b) {
  219.             ld ang = atan2(x.y - a[i].y, x.x - a[i].x);
  220.             c.pb(mp(ang, mp(-1, x)));
  221.         }
  222.  
  223.         sort(c.begin(), c.end());
  224.  
  225.         int s = c.size();
  226.         for (int i = 0; i < s; i++) {
  227.             c.pb(c[i]);
  228.         }
  229.  
  230.         for (int j = 0; j < c.size() / 2; j++) {
  231.  
  232.             if (c[j].snd.fst < 0) {
  233.                 continue;
  234.             }
  235.  
  236.             auto v = c[j].snd.snd;
  237.  
  238.             pt f = v + (v - u);
  239.  
  240.             for (int h = 0; h < c.size() / 2; h++) {
  241.  
  242.                 ll d = ((v - u) ^ (c[h + j].snd.snd - u));
  243.  
  244.                 if (d == 0) {
  245.                     continue;
  246.                 } else if (d < 0) {
  247.                     break;
  248.                 }
  249.  
  250.                 int k = h;
  251.  
  252.                 while (k < c.size() / 2 && abs(c[h + j].fst - c[k + j].fst) < eps) {
  253.                     k++;
  254.                 }
  255.  
  256.                 pt nf = f;
  257.  
  258.                 for (int w = h; w < k; w++) {
  259.  
  260.                     pt p = c[w + j].snd.snd;
  261.  
  262.                     if (c[w + j].snd.fst > 0) {
  263.  
  264.                         ll g = (f - v) ^ (p - v);
  265.  
  266.                         if (g >= 0) {
  267.                             ans++;
  268.                         }
  269.                     } else {
  270.                         ll g = (nf - v) ^ (p - v);
  271.  
  272.                         if (g >= 0) {
  273.                             nf = p;
  274.                         }
  275.                     }
  276.                 }
  277.  
  278.                 f = nf;
  279.  
  280.                 h = k - 1;
  281.             }
  282.         }
  283.     }
  284.  
  285.     assert(ans % 3 == 0);
  286.     ans /= 3;
  287.  
  288.     //assert(ans == brute(a, b));
  289.  
  290.     cout << ans << endl;
  291.     //cout << brute(a, b) << endl;
  292.     //goto retry;
  293.  
  294.     cerr << (ld)clock() / CLOCKS_PER_SEC << endl;
  295.  
  296.     return 0;
  297. }
Advertisement
Add Comment
Please, Sign In to add comment