QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#935049 | #2297. Flatland Olympics | AngelOlan | WA | 1ms | 3712kb | C++23 | 2.2kb | 2025-03-15 12:09:01 | 2025-03-15 12:09:02 |
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) { return p.y > 0 || (p.y == 0 && p.x < 0); }
inline void polarSortAround(Point o, vector<Point>& P, bool inv = false) {
sort(P.begin(), P.end(), [&](Point p, Point q) {
return make_tuple(half(p - o), 0, (p - o).sq()) < make_tuple(half(q - o), (p - o).cross(q - o), (q - o).sq());
});
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) {
polarSortAround(a, P, inv);
Point dir = b - a;
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);
if (e.x < 0) {
e.x *= -1;
for (Point& p : P) {
p.x *= -1;
}
}
if (e.y < 0) {
e.y *= -1;
for (Point& p : P) {
p.y *= -1;
}
}
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';
}
詳細信息
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: 0
Accepted
time: 1ms
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: 3584kb
input:
0 0 2 0 3 1 1 2 2 2 1
output:
2
result:
ok single line: '2'
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3712kb
input:
0 0 2 0 3 1 1 0 2 0 1
output:
1
result:
wrong answer 1st lines differ - expected: '2', found: '1'