QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#604247 | #7803. H-Shaped Figures | surgutti | RE | 0ms | 3740kb | C++20 | 3.8kb | 2024-10-02 02:35:16 | 2024-10-02 02:35:16 |
Judging History
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