QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#935105 | #2297. Flatland Olympics | AngelOlan | WA | 2ms | 3968kb | C++23 | 2.2kb | 2025-03-15 12:46:34 | 2025-03-15 12:46:43 |
Judging History
answer
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
// Pura Gente del Coach Moy y de la Alexbriza
using ll = long long;
using T = ll;
struct Point {
int x, y;
Point() {}
Point(int x, int y) : x(x), y(y) {}
void read() {
cin >> x >> y;
}
void print() {
cout << x << ' ' << y << '\n';
}
T sq() { return (T)x * x + (T)y * y; }
T dot(Point p) { return (T)x * p.x + (T)y * p.y; }
T cross(Point p) const { return (T)x * p.y - (T)y * p.x; }
Point operator-(Point p) const { return Point(x - p.x, y - p.y); }
};
T orient(Point a, Point b) { return a.cross(b); }
int half(Point p, Point v) { return v.cross(p) < 0 || (v.cross(p) == 0 && v.dot(p) < 0); }
inline void polarSortAround(Point o, Point dir, vector<Point>& P, bool inv = false) {
sort(P.begin(), P.end(), [&](Point p, Point q) -> bool {
auto ta = make_tuple(half(p - o, dir), 0);
auto tb = make_tuple(half(q - o, dir), (p - o).cross(q - o));
if (ta != tb) {
return ta < tb;
}
return ((p - o).sq() < (q - o).sq()) ^ inv;
});
if (inv) {
reverse(P.begin(), P.end());
}
}
template <class T>
using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll f(Point a, Point b, vector<Point>& P, bool inv = false) {
Point dir = b - a;
polarSortAround(a, dir, P, inv);
oset<ll> oset;
ll ret = 0;
for (Point p : P) {
T dot = dir.dot(p - a);
int ord = int(oset.order_of_key(dot + inv));
ret += ord;
oset.insert(dot);
}
return ret;
}
ll gauss(int n) {
return (ll)n * (n + 1) >> 1;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
Point s, e;
s.read(), e.read();
int n;
cin >> n;
vector<Point> P(n);
for (Point& p : P) {
p.read();
p = p - s;
}
e = (e - s);
s = (s - s);
vector<int> inLine(2);
vector<Point> L, R;
for (Point& p : P) {
T ori = orient(e, p);
if (ori > 0) {
L.push_back(p);
} else if (ori < 0) {
R.push_back(p);
} else {
++inLine[e.dot(p) < 0];
}
}
ll ans = gauss(inLine[0] - 1) + gauss(inLine[1] - 1) + f(s, e, L) + f(s, e, R, true) + f(e, s, L, true) + f(e, s, R);
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
0 0 1 0 2 -1 0 2 0
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
0 0 1 0 4 -1 0 -2 0 2 0 3 0
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
0 0 2 0 3 1 1 2 2 2 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
0 0 2 0 3 1 1 0 2 0 1
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
5 0 6 0 10 8 0 3 0 2 0 11 0 4 0 9 0 0 0 10 0 7 0 1 0
output:
20
result:
ok single line: '20'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
0 0 1 0 3 1 1 1 2 1 3
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
0 0 4 3 2 5 0 3 0
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
0 0 4 3 2 3 0 5 0
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
-1000000000 1000000000 1000000000 999999999 2 -1000000000 -1000000000 999999999 999999998
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
999999999 -1000000000 1000000000 999999999 2 -1000000000 -1000000000 999999999 999999998
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
999999997 999999999 -999999998 -999999998 6 999999999 999999998 1000000000 999999997 999999997 999999996 -999999997 -999999997 -999999999 -999999999 -1000000000 -1000000000
output:
5
result:
ok single line: '5'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
-1000000000 -1000000000 -999999999 -999999999 9 1000000000 1000000000 999999999 999999999 999999998 999999998 1000000000 999999999 999999999 999999998 999999998 999999997 999999999 1000000000 999999998 999999999 999999997 999999998
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
-3 -15 15 3 6 0 4 -4 0 -5 1 -1 5 -2 2 -3 3
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
-2 -8 8 2 5 -4 1 0 2 -3 0 -1 3 -2 4
output:
4
result:
ok single line: '4'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
1399 -1293 -2636 1822 1000 -510452 -660980 -126684 -163868 -71237 -92045 -2084 -2468 -443168 -573824 -499861 -647261 -222626 -288146 -421363 -545579 -238824 -309128 -115470 -149342 -267482 -346250 -355325 -460037 -273089 -353513 -7691 -9731 -28873 -37169 -63138 -81554 -92419 -119483 -463727 -600455 ...
output:
499500
result:
ok single line: '499500'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3840kb
input:
2024 48517 -6336 -100443 2500 4054 -20413 25109 -48138 21969 -16503 11444 -46388 16584 -7353 16289 -47643 18964 -35013 9659 -25643 13579 -25863 -2496 -49538 43629 -33448 37804 -32138 26494 -5943 35944 -47763 5739 -25423 17104 -50638 39984 -28328 34369 -40793 19239 -30113 40789 -49018 5794 -24443 384...
output:
2514840
result:
ok single line: '2514840'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
350 2230 1241 -7802 1000 2224211 195148 1335173 114349 406676 32803 429557 33916 2330996 203713 73715 4150 709541 58783 878180 74680 2148596 187513 2700437 235606 1901525 164650 809699 69517 640229 52627 2005331 175708 185060 13120 454100 37015 1171925 99850 2173301 188788 1715315 149950 1357061 116...
output:
426462
result:
ok single line: '426462'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
67176 -131382 -137128 265474 2500 -76892 101002 -36326 -5844 -67830 -30948 -63540 92326 -61326 16828 -156390 63408 -51544 86284 -23972 32726 -35526 1232 -160946 37738 -70122 51174 -53918 62848 -166448 54898 -170230 38512 -116262 106280 -91246 44742 -52920 15602 -36020 43184 -24538 5778 -93874 -32138...
output:
2511086
result:
ok single line: '2511086'
Test #19:
score: -100
Wrong Answer
time: 0ms
memory: 3840kb
input:
-247940590 -800864001 -376339814 357558744 1000 -381895428 -268441834 587795571 401546767 -233436735 -505362442 -769956233 -716358227 -35039180 789288175 886928299 -255208074 695681326 548764540 -435121059 -552564037 605862324 -706572950 -80805696 -171753153 -589436010 -269238096 110878492 781059697...
output:
91945
result:
wrong answer 1st lines differ - expected: '77951', found: '91945'