QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#604247#7803. H-Shaped FiguressurguttiRE 0ms3740kbC++203.8kb2024-10-02 02:35:162024-10-02 02:35:16

Judging History

你现在查看的是最新测评结果

  • [2024-10-02 02:35:16]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3740kb
  • [2024-10-02 02:35:16]
  • 提交

answer

// Author: Olaf Surgut (surgutti)
// Created on 01-10-2024 19:41:35
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

#define endl '\n'
#define st first
#define nd second
#define pb push_bask
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define ROF(i, b, a) for (int i = (b); i >= (a); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ll long long

struct Point {
	int x, y;

	int pp, qq, typ;

	void read() {
		cin >> x >> y;
	}

	Point operator- (Point other) const {
		return Point{x - other.x, y - other.y, -1, -1, -1};
	}
};

ostream& operator<< (ostream&os, Point P) {
	return os << "(" << P.x << "," << P.y << "|" << P.typ << ")";
}

ll det(Point A, Point B) {
	return (ll) A.x * B.y - (ll) A.y * B.x;
}

ll dot(Point A, Point B) {
	return (ll) A.x * B.x + (ll) A.y * B.y;
}

int half(Point A, Point v) {
	ll x = dot(v, v);
	ll y = det(v, A);

	if (x >= 0 && y >= 0)
		return 1;
	if (x <= 0 && y >= 0)
		return 2;
	if (x <= 0 && y <= 0)
		return 3;
	if (x >= 0 && y <= 0)
		return 4;
	assert(false);

	return -1;
}

int angle_cmp(Point A, Point B, Point v) {
	int hA = half(A, v);
	int hB = half(B, v);
	if (hA != hB)
		return hA < hB;
	return det(A, B) > 0;	
}

vector<Point> pts[2];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int tt;
	cin >> tt;
	while (tt--) {
		Point P, Q;
		P.read(), Q.read();

		int n;
		cin >> n;
		
		int L = 0, R = 0;
		REP(i, n) {
			Point T, S;
			T.read(), S.read();
			
			if (dot(P - S, T - S) > 0 &&
				dot(P - T, S - T) > 0 &&
				det(P - S, T - S) == 0 &&
				det(P - Q, T - S) != 0) {
				T.typ = 0;
				S.typ = 0;
				pts[det(Q - P, T - P) < 0].eb(T);
				pts[det(Q - P, S - P) < 0].eb(S);
				L++;
				debug("L", T, S);
			}
			
			if (dot(Q - S, T - S) > 0 &&
				dot(Q - T, S - T) > 0 &&
				det(Q - S, T - S) == 0 &&
				det(Q - P, T - S) != 0) {
				T.typ = 1;
				S.typ = 1;
				pts[det(P - Q, T - Q) > 0].eb(T);
				pts[det(P - Q, S - Q) > 0].eb(S);
				R++;
				debug("R", T, S);
			}
		}

		ll ans = (ll) L * R;
		debug(L, R, ans);

		REP(h, 2) {
			debug(h);
			debug(pts[h]);

			sort(all(pts[h]), 
				[&](Point X, Point Y) {
					return angle_cmp(X - P, Y - P, Q - P);
				}
			);

			debug("by P", pts[h]);
			debug(P, Q - P);

			pts[h][0].pp = 1;
			FOR(i, 1, sz(pts[h]) - 1) {
				int diff = angle_cmp(pts[h][i - 1] - P, pts[h][i] - P, Q - P);
				pts[h][i].pp = pts[h][i - 1].pp + diff;
			}
			
			sort(all(pts[h]), 
				[&](Point X, Point Y) {
					return angle_cmp(X - Q, Y - Q, Q - P);
				}
			);

			pts[h][0].qq = 1;
			FOR(i, 1, sz(pts[h]) - 1) {
				int diff = angle_cmp(pts[h][i - 1] - Q, pts[h][i] - Q, Q - P);
				pts[h][i].qq = pts[h][i - 1].qq + diff;
			}

			sort(all(pts[h]), 
				[&](Point X, Point Y) {
					if (X.pp != Y.pp)
						return X.pp < Y.pp;
					if (X.qq != Y.qq)
						return X.qq < Y.qq;
					return (X.typ == h) > (Y.typ == h);
				}
			);

			vector<int> bit(sz(pts[h]) + 1);

			for (Point E : pts[h]) {
				debug(E, E.pp, E.qq);

				int i = E.qq;
				if (E.typ == h) {
					while (i < sz(bit)) {
						bit[i]++;
						i += i & -i;
					}
				}
				else {
					while (i > 0) {
						ans -= bit[i];
						i -= i & -i;
					}
				}
			}

			swap(P, Q);
		}

		cout << ans << '\n';
	
		REP(i, 2) {
			pts[i].clear();
		}
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3740kb

input:

1
0 0 4 0
8
0 0 2 1
-1 -1 2 2
3 3 5 -3
0 2 6 -1
2 -2 5 1
-1 1 3 -3
-1 0 2 0
-1 -1 2 2

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: -100
Runtime Error

input:

1
-1 0 0 1
2
1 1 0 -1
1 1 0 1

output:


result: