QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#935101 | #2297. Flatland Olympics | AngelOlan | WA | 1ms | 3584kb | C++23 | 2.1kb | 2025-03-15 12:45:21 | 2025-03-15 12:45:22 |
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 = f(s, e, L) + f(s, e, R, true) + f(e, s, L, true) + f(e, s, R);
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
0 0 1 0 2 -1 0 2 0
output:
0
result:
ok single line: '0'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3584kb
input:
0 0 1 0 4 -1 0 -2 0 2 0 3 0
output:
0
result:
wrong answer 1st lines differ - expected: '2', found: '0'