Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <string.h>
- #include <queue>
- #include <math.h>
- #include <cmath>
- #include <map>
- #include <set>
- #include <vector>
- #include <algorithm>
- #include <bitset>
- #include <list>
- #include <ctype.h>
- #include <cassert>
- #include <stack>
- #include <fstream>
- #include <unordered_map>
- #include <unordered_set>
- #include <ctime>
- #include <functional>
- #include <ctime>
- using namespace std;
- #define snd second
- #define fst first
- #define mp make_pair
- #define ll long long
- #define ull unsigned long long
- #define ld long double
- #define pb push_back
- #define left _left
- #define right _right
- const ld pi = 3.14159265359;
- template<typename T>
- T abs(T x) {
- return x > 0 ? x : -x;
- }
- template<typename T>
- T sqr(T x) {
- return x * x;
- }
- template<typename T>
- void chmin(T &x, T y) {
- x = min(x, y);
- }
- template<typename T>
- void chmax(T &x, T y) {
- x = max(x, y);
- }
- template<typename U, typename V>
- ostream& operator << (ostream &s, const pair<U, V> &x) {
- s << "(" << x.fst << ", " << x.snd << ")";
- return s;
- }
- template<typename U>
- ostream& operator << (ostream &s, const vector<U> &x) {
- s << "[";
- bool was = false;
- for (auto it : x) {
- if (was) {
- s << ", ";
- }
- was = true;
- s << it;
- }
- s << "]";
- return s;
- }
- //-----------------------------------------------------------------------------
- const ld eps = 1e-9;
- struct pt {
- ll x, y;
- pt(ll _x = 0, ll _y = 0) {
- x = _x, y = _y;
- }
- pt operator + (const pt &o) const {
- return pt(x + o.x, y + o.y);
- }
- pt operator - (const pt &o) const {
- return pt(x - o.x, y - o.y);
- }
- ll operator ^ (const pt &o) const {
- return x * o.y - y * o.x;
- }
- ll operator % (const pt &o) const {
- return x * o.x + y * o.y;
- }
- ld len() {
- return sqrt(sqr(x) + sqr(y));
- }
- static pt read() {
- ll x, y;
- cin >> x >> y;
- //x = rand() % 1000, y = rand() % 100;
- return pt(x, y);
- }
- bool operator < (const pt &o) const {
- return mp(x, y) < mp(o.x, o.y);
- }
- };
- ll area(pt a, pt b, pt c) {
- return abs((b - a) ^ (c - a));
- }
- int brute(vector<pt> a, vector<pt> b) {
- int ans = 0;
- for (auto u : a) {
- for (auto v : a) {
- for (auto w : a) {
- ll s = area(u, v, w);
- if (!s) {
- continue;
- }
- bool bad = false;
- for (auto p : b) {
- bad |=
- area(u, v, p) + area(u, w, p) + area(v, w, p) == s &&
- area(u, v, p) && area(u, w, p) && area(v, w, p);
- }
- if (!bad) {
- ans++;
- }
- }
- }
- }
- assert(ans % 6 == 0);
- return ans / 6;
- }
- void gen() {
- ofstream out("a.in");
- int n = 500, m = 500;
- out << n << " " << m << endl;
- for (int i = 0; i < n; i++) {
- int x = rand() % 1000, y = rand() % 1000;
- out << x << " " << y << endl;
- }
- for (int i = 0; i < m; i++) {
- int x = rand() % 1000, y = rand() % 1000;
- out << x << " " << y << endl;
- }
- out.close();
- }
- int main() {
- srand(time(NULL));
- retry:
- #ifdef LOCAL
- gen();
- //cerr << 1 << endl;
- freopen("a.in", "r", stdin);
- #else
- //freopen("fract.in", "r", stdin);
- //freopen("fract.out", "w", stdout);
- #endif
- vector<pt> a, b;
- int n, m;
- cin >> n >> m;
- //n = 500, m = 500;
- for (int i = 0; i < n; i++) {
- a.pb(pt::read());
- }
- for (int i = 0; i < m; i++) {
- b.pb(pt::read());
- }
- int ans = 0;
- for (int i = 0; i < n; i++) {
- auto u = a[i];
- //cerr << i << endl;
- vector<pair<ld, pair<int, pt>>> c;
- int qty = 1;
- for (auto x : a) {
- if (qty != i + 1) {
- ld ang = atan2(x.y - a[i].y, x.x - a[i].x);
- c.pb(mp(ang, mp(qty, x)));
- }
- qty++;
- }
- for (auto x : b) {
- ld ang = atan2(x.y - a[i].y, x.x - a[i].x);
- c.pb(mp(ang, mp(-1, x)));
- }
- sort(c.begin(), c.end());
- int s = c.size();
- for (int i = 0; i < s; i++) {
- c.pb(c[i]);
- }
- for (int j = 0; j < c.size() / 2; j++) {
- if (c[j].snd.fst < 0) {
- continue;
- }
- auto v = c[j].snd.snd;
- pt f = v + (v - u);
- for (int h = 0; h < c.size() / 2; h++) {
- ll d = ((v - u) ^ (c[h + j].snd.snd - u));
- if (d == 0) {
- continue;
- } else if (d < 0) {
- break;
- }
- int k = h;
- while (k < c.size() / 2 && abs(c[h + j].fst - c[k + j].fst) < eps) {
- k++;
- }
- pt nf = f;
- for (int w = h; w < k; w++) {
- pt p = c[w + j].snd.snd;
- if (c[w + j].snd.fst > 0) {
- ll g = (f - v) ^ (p - v);
- if (g >= 0) {
- ans++;
- }
- } else {
- ll g = (nf - v) ^ (p - v);
- if (g >= 0) {
- nf = p;
- }
- }
- }
- f = nf;
- h = k - 1;
- }
- }
- }
- assert(ans % 3 == 0);
- ans /= 3;
- //assert(ans == brute(a, b));
- cout << ans << endl;
- //cout << brute(a, b) << endl;
- //goto retry;
- cerr << (ld)clock() / CLOCKS_PER_SEC << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment