QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661863 | #7803. H-Shaped Figures | ucup-team1001 | Compile Error | / | / | C++23 | 7.0kb | 2024-10-20 18:35:54 | 2024-10-20 18:35:55 |
Judging History
This is the latest submission verdict.
- [2024-10-20 18:35:55]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-10-20 18:35:54]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define irep(i, l, r) for(int i = l; i <= r; ++ i)
#define drep(i, r, l) for(int i = r; i >= l; -- i)
const int mod = 998244353;
typedef long long LD;
int sgn(LD x) {
if (x > 0)return 1;
if (x == 0)return 0;
return -1;
}
struct frac {
LD a, b;// a / sqrt(b)
frac(LD aa = 0, LD bb = 1) {
a = aa, b = bb;
}
bool operator==(const frac &A) const {
if (sgn(a) != sgn(A.a))return false;
__int128 AA = __int128(a) * a, BB = b, CC = __int128(A.a) * A.a, DD = A.b;
__int128 D = gcd(AA, BB), E = gcd(CC, DD);
AA /= D, BB /= D, CC /= E, DD /= E;
return make_pair(AA, BB) == make_pair(CC, DD);
}
bool operator<(const frac &A) const {
return ((long double)(1.0)* a / sqrtl(b)) < ((long double)(1.0)* A.a / sqrtl(A.b));
}
};
struct point {
LD x, y;
point(LD xx = 0, LD yy = 0) {
x = xx, y = yy;
}
friend LD dot(const point &a, const point &b) {
return a.x * b.x + a.y * b.y;
}
friend LD det(const point &a, const point &b) {
return a.x * b.y - a.y * b.x;
}
bool operator==(const point &a) const {
return a.x == x and a.y == y;
}
point operator-(const point &a) const {
return {x - a.x, y - a.y};
}
};
struct bit {
int n;
vector<int> t;
bit(int m) {
n = m;
t.resize(n + 10);
}
int ask(int x) {
int ans = 0;
for (; x; x -= x & -x)
ans += t[x];
return ans;
}
void add(int x, int v) {
for (; x <= n; x += (x & -x))
t[x] += v;
}
};
ll count_2d(int n, vector<array<int, 2>> a, vector<array<int, 2>> b) {
bit T(n);
vector<array<int, 3>> arr;
for (auto [i, j]: a) {
arr.push_back({i, 1, j});
}
for (auto [i, j]: b) {
arr.push_back({i, 0, j});
}
sort(arr.begin(), arr.end());
ll sum = 0;
for (auto [I, tp, x]: arr) {
if (tp == 0)sum += T.ask(x);
else T.add(x, 1);
}
return sum;
}
void solve() {
int n;
point P, Q;
cin >> P.x >> P.y >> Q.x >> Q.y;
// swap(P, Q);
cin >> n;
vector<point> aa, bb, a, b;
ll sum1 = 0, sum2 = 0;
ll ans = 0;
irep(i, 0, n - 1) {
point L, R;
cin >> L.x >> L.y >> R.x >> R.y;
// cerr << det(L - P, R - P) << ' ' << dot(L - P, R - P) << ' ' << det(L - Q, R - Q) << endl;
if (det(L - P, R - P) == 0 and dot(L - P, R - P) < 0 and det(L - Q, R - Q) != 0)
aa.push_back(L), aa.push_back(R);
if (det(L - Q, R - Q) == 0 and dot(L - Q, R - Q) < 0 and det(L - P, R - P) != 0)
bb.push_back(L), bb.push_back(R);
}
ans = (1ll * aa.size() * bb.size()) / 4;
for (auto A: aa) {
if (det(A - Q, P - Q) > 0)
a.push_back(A);
}
for (auto A: bb) {
if (det(A - Q, P - Q) > 0)
b.push_back(A);
}
vector<pair<frac, int>> cosA;
vector<frac> cosALL;
vector<array<int, 2>> TA, TB;
for (auto p: a) {
cosA.push_back({{dot(p - Q, P - Q), dot(p - Q, p - Q)}, 0});
cosALL.emplace_back(dot(p - P, Q - P), dot(p - P, p - P));
cosALL.emplace_back(dot(p - Q, P - Q), dot(p - Q, p - Q));
}
for (auto p: b) {
cosA.push_back({{dot(p - Q, P - Q), dot(p - Q, p - Q)}, 1});
cosALL.emplace_back(dot(p - P, Q - P), dot(p - P, p - P));
cosALL.emplace_back(dot(p - Q, P - Q), dot(p - Q, p - Q));
}
sort(cosA.begin(), cosA.end());
sort(cosALL.begin(), cosALL.end());
reverse(cosA.begin(), cosA.end());
cosALL.erase(unique(cosALL.begin(), cosALL.end()), cosALL.end());
ll typeB = 0;
for (auto [FR, tp]: cosA) {
// cerr << FR.a << ' ' << FR.b << endl;
// cerr << tp << ' ' << endl;
if (tp)++typeB;
else sum1 += typeB;
}
for (auto p: a) {
frac t1 = {dot(p - P, Q - P), dot(p - P, p - P)},
t2 = {dot(p - Q, P - Q), dot(p - Q, p - Q)};
TA.push_back({int(lower_bound(cosALL.begin(), cosALL.end(), t1) - cosALL.begin()) + 1,
int(lower_bound(cosALL.begin(), cosALL.end(), t2) - cosALL.begin()) + 1});
}
for (auto p: b) {
frac t1 = {dot(p - P, Q - P), dot(p - P, p - P)},
t2 = {dot(p - Q, P - Q), dot(p - Q, p - Q)};
TB.push_back({int(lower_bound(cosALL.begin(), cosALL.end(), t1) - cosALL.begin()) + 1,
int(lower_bound(cosALL.begin(), cosALL.end(), t2) - cosALL.begin()) + 1});
}
sum2 += count_2d(cosALL.size() + 3, TA, TB);
cosA.clear(), cosALL.clear(), TA.clear(), TB.clear(), a.clear(), b.clear();
//---------------------------------------------------------------------------------------------------------
for (auto A: aa) {
if (det(A - Q, P - Q) < 0)
a.push_back(A);
}
for (auto A: bb) {
if (det(A - Q, P - Q) < 0)
b.push_back(A);
}
for (auto p: a) {
cosA.push_back({{dot(p - Q, P - Q), dot(p - Q, p - Q)}, 0});
cosALL.emplace_back(dot(p - P, Q - P), dot(p - P, p - P));
cosALL.emplace_back(dot(p - Q, P - Q), dot(p - Q, p - Q));
}
for (auto p: b) {
cosA.push_back({{dot(p - Q, P - Q), dot(p - Q, p - Q)}, 1});
cosALL.emplace_back(dot(p - P, Q - P), dot(p - P, p - P));
cosALL.emplace_back(dot(p - Q, P - Q), dot(p - Q, p - Q));
}
sort(cosA.begin(), cosA.end());
reverse(cosA.begin(), cosA.end());
sort(cosALL.begin(), cosALL.end());
cosALL.erase(unique(cosALL.begin(), cosALL.end()), cosALL.end());
typeB = 0;
for (auto [FR, tp]: cosA) {
if (tp)++typeB;
else sum1 += typeB;
}
for (auto p: a) {
frac t1 = {dot(p - P, Q - P), dot(p - P, p - P)},
t2 = {dot(p - Q, P - Q), dot(p - Q, p - Q)};
TA.push_back({int(lower_bound(cosALL.begin(), cosALL.end(), t1) - cosALL.begin()) + 1,
int(lower_bound(cosALL.begin(), cosALL.end(), t2) - cosALL.begin()) + 1});
}
for (auto p: b) {
frac t1 = {dot(p - P, Q - P), dot(p - P, p - P)},
t2 = {dot(p - Q, P - Q), dot(p - Q, p - Q)};
TB.push_back({int(lower_bound(cosALL.begin(), cosALL.end(), t1) - cosALL.begin()) + 1,
int(lower_bound(cosALL.begin(), cosALL.end(), t2) - cosALL.begin()) + 1});
}
sum2 += count_2d(cosALL.size() + 3, TA, TB);
cout << ans - sum1 + sum2 << '\n';
/*
4
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
0 0 4 0
2
-1 -1 2 2
3 1
5 -1
0 0 4 0
2
-1 -1 2 2
1 3
5 -1
0 0 4 0
2
-1 -1 2 2
1 1 7 -1
6
1
0
0
*/
}
int main() {
frac A = {371884131150, 64678868005775570}, B = {2430385351992, 576903514247757000};
ios::sync_with_stdio(false), cin.tie(0);
int T = 1;
cin >> T;
while (T--)solve();
return 0;
}
Details
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:58, from answer.code:1: /usr/include/c++/13/numeric: In instantiation of ‘constexpr std::common_type_t<_Tp1, _Tp2> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; common_type_t<_Tp1, _Tp2> = __int128]’: answer.code:28:25: required from here /usr/include/c++/13/numeric:166:21: error: static assertion failed: std::gcd arguments must be integers 166 | static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>, | ^~~~~~~~~~~~~~~~~~ /usr/include/c++/13/numeric:166:21: note: ‘std::is_integral_v<__int128>’ evaluates to false In file included from /usr/include/c++/13/bits/stl_pair.h:60, from /usr/include/c++/13/bits/stl_algobase.h:64, from /usr/include/c++/13/algorithm:60, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51: /usr/include/c++/13/type_traits: In instantiation of ‘struct std::make_unsigned<__int128>’: /usr/include/c++/13/type_traits:1983:11: required by substitution of ‘template<class _Tp> using std::make_unsigned_t = typename std::make_unsigned::type [with _Tp = __int128]’ /usr/include/c++/13/numeric:173:24: required from ‘constexpr std::common_type_t<_Tp1, _Tp2> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; common_type_t<_Tp1, _Tp2> = __int128]’ answer.code:28:25: required from here /usr/include/c++/13/type_traits:1836:62: error: invalid use of incomplete type ‘class std::__make_unsigned_selector<__int128, false, false>’ 1836 | { typedef typename __make_unsigned_selector<_Tp>::__type type; }; | ^~~~ /usr/include/c++/13/type_traits:1744:11: note: declaration of ‘class std::__make_unsigned_selector<__int128, false, false>’ 1744 | class __make_unsigned_selector; | ^~~~~~~~~~~~~~~~~~~~~~~~