Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ld = long double;
- ld eps = 1e-9;
- bool equal(ld a, ld b) {
- return fabs(a - b) < eps;
- }
- struct pt {
- ld x, y;
- pt(ld _x = 0, ld _y = 0) {
- x = _x;
- y = _y;
- }
- };
- pt operator - (pt a, pt b) { return {a.x - b.x, a.y - b.y}; }
- ld operator * (pt a, pt b) { return a.x * b.y - b.x * a.y; }
- ld operator ^ (pt a, pt b) { return a.x * b.x + a.y * b.y; }
- bool operator == (pt a, pt b) { return equal(a.x, b.x) && equal(a.y, b.y); }
- bool operator < (pt a, pt b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; }
- struct line {
- ld a, b, c;
- line(ld _a = 0, ld _b = 0, ld _c = 0) {
- a = _a, b = _b, c = _c;
- }
- };
- bool inter(line m, line n, pt & res) {
- ld zn = (pt(m.a, m.b) * pt(n.a, n.b));
- if (equal(zn, 0)) return 0;
- res.x = -(pt(m.c, m.b) * pt(n.c, n.b)) / zn;
- res.y = -(pt(m.a, m.c) * pt(n.a, n.c)) / zn;
- return 1;
- }
- line toline(pt a, pt b) {
- return line(a.y - b.y, b.x - a.x, a * b);
- }
- bool cmp(pt a, pt b) {
- return a * b > 0;
- }
- bool hull(pt a, pt b) {
- if (a.y != b.y)
- return a.y < b.y;
- return a.x < b.x;
- }
- struct polygon {
- vector <pt> data;
- void kek() {
- sort(data.begin(), data.end());
- data.erase(unique(data.begin(), data.end()), data.end());
- pt f = *min_element(data.begin(), data.end(), hull);
- for (auto &i : data) i = i - f;
- vector <pt> newdata;
- pt beg(0.0, 0.0);
- for (auto &i : data) if (!(i == beg)) newdata.push_back(i);
- sort(newdata.begin(), newdata.end(), cmp);
- newdata.insert(newdata.begin(), beg);
- f = {-f.x, -f.y};
- for (auto &i : newdata) i = i - f;
- swap(data, newdata);
- }
- };
- bool on_line(pt a, pt b, pt c) {
- return (equal((b - a) * (c - a), 0) && ((c - a) ^ (c - b)) + 4 * 1e-14 < 0);
- }
- bool cut(polygon &a, line t, polygon &b, polygon &c) {
- bool flag[2] = {0, 0};
- for (auto &i : a.data) {
- ld value = (t.a * i.x + t.b * i.y + t.c);
- if (equal(value, 0.0)) {
- b.data.push_back(i);
- c.data.push_back(i);
- }
- else if (value + 4 * 1e-14 < 0) {
- b.data.push_back(i);
- flag[0] = 1;
- }
- else {
- c.data.push_back(i);
- flag[1] = 1;
- }
- }
- if (!(flag[0] & flag[1])) return 0;
- for (int i = 0; i < a.data.size(); ++i) {
- int nxt = (i + 1) % a.data.size();
- line k = toline(a.data[i], a.data[nxt]);
- pt cross;
- if (inter(k, t, cross)) {
- if (on_line(a.data[i], a.data[nxt], cross)) {
- b.data.push_back(cross);
- c.data.push_back(cross);
- }
- }
- }
- b.kek(); c.kek();
- return 1;
- }
- void solve() {
- ld x, y;
- cin >> x >> y;
- vector <polygon> base;
- base.push_back({{{0, 0}, {0, y}, {x, y}, {x, 0}}});
- int n; cin >> n;
- while (n--) {
- ld a, b, c;
- cin >> a >> b >> c;
- vector <polygon> add;
- vector <char> mark(base.size(), 0);
- for (int i = 0; i < base.size(); ++i) {
- polygon rofl, fun;
- if (cut(base[i], line(a, b, c), rofl, fun)) {
- add.push_back(rofl);
- add.push_back(fun);
- mark[i] = 1;
- }
- }
- vector <polygon> newbase;
- for (int i = 0; i < base.size(); ++i) if (!mark[i]) newbase.push_back(base[i]);
- for (auto i : add) newbase.push_back(i);
- swap(base, newbase);
- }
- int res = 0;
- for (auto i : base) if (i.data.size() == 3) res++;
- cout << res << '\n';
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement