QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721676 | #5538. Magical Barrier | zijinjun# | WA | 1ms | 3728kb | C++17 | 3.8kb | 2024-11-07 16:35:22 | 2024-11-07 16:35:22 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <unordered_set>
#include <functional>
#include <stack>
#include <unordered_map>
#include <map>
#include <cmath>
using namespace std;
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (c > '9' || c < '0')
f = c == '-' ? -1 : 1, c = getchar();
while (c >= '0' && c <= '9')
x = x * 10 + c - 48, c = getchar();
return x * f;
}
using i64 = long long;
using u64 = unsigned long long;
using pii = pair<int, int>;
using pll = pair<i64, i64>;
#define int long long
struct Point {
i64 x, y;
Point (int _x = 0, int _y = 0) {
x = _x, y = _y;
}
};
using Vector = Point;
Point operator + (Point a, Point b) {
return Point(a.x + b.x, a.y + b.y);
}
Point operator - (Point a, Point b) {
return Point(a.x - b.x, a.y - b.y);
}
int sgn(int x) {
return (x > 0) - (x < 0);
}
bool operator < (Point a, Point b) {
return sgn(a.x - b.x) < 0 || ((sgn(a.x-b.x) == 0) && sgn(a.y - b.y) < 0);
}
i64 Dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
i64 Cross (Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
const int N = 1010;
Point hull[N], p[N];
int n;
int get_hull() {
sort(p, p + n);
int v = 0;
for (int i = 0; i < n; ++i) {
while (v > 1 && sgn(Cross(hull[v - 1] - hull[v - 2], p[i] - hull[v - 1])) <= 0)
v--;
hull[v++] = p[i];
}
int j = v;
for (int i = n - 2; i >= 0; --i) {
while (v > j && sgn(Cross(hull[v - 1] - hull[v - 2], p[i] - hull[v - 1])) <= 0)
--v;
hull[v++] = p[i];
}
if (n > 1) v--;
return v;
}
int get_dimension(const Vector &x, const Vector &y) {
int dot = sgn(Dot(x, y));
int cross = sgn(Cross(x, y));
if (cross == 0 && dot == 0)
return 0;
if (cross == 0 && dot > 0)
return 1;
if (cross > 0 && dot > 0)
return 2;
if (cross > 0 && dot <= 0)
return 3;
if (cross == 0 && dot < 0)
return 4;
if (cross < 0 && dot <= 0)
return 5;
return 6; // cross < 0, dot > 0
}
struct cmp {
Point p;
Vector v;
cmp(const Point &p0, const Vector &v0) {
p = p0;
v = v0;
}
bool operator()(const Point &a, const Point &b) {
int da = get_dimension(v, a - p);
int db = get_dimension(v, b - p);
if (da != db)
return da < db;
return sgn(Cross(a - p, b - p)) > 0;
}
};
signed main() {
n = read();
if (n <= 3) {
cout << 0 << endl;
return 0;
}
for (int i = 0; i < n; ++i)
p[i].x = read(), p[i].y = read();
int m = get_hull();
// cout << m << " : ";
// for (int i = 0; i < m; ++i)
// cout << hull[i].x <<" "<< hull[i].y<<endl;
int ans = 0;
for (int i = 0; i < m; i++) {
sort(p, p + n, cmp(hull[i], hull[(i + 1) % m] - hull[i]));
int sum = 0;
int cnt1 = 0, cnt2 = 0, cnt3 = 0; // 下面的,中间的,上面的
// j->hull k1->p k2->p
int k1 = 1, k2 = 1;
for (int j = (i + 1) % m; j != i; j = (j + 1) % m) {
k2 = max(k2, k1);
while (k1 < n && Cross(hull[j] - hull[i], p[k1] - hull[i]) < 0)
k1++;
while (k2 < n && Cross(hull[j] - hull[i], p[k2] - hull[i]) <= 0)
k2++;
cnt2 = k2 - k1 - 1;
cnt1 = max(0ll, k1 - 1);
cnt3 = n - k2;
sum = (cnt1 + cnt3) * cnt2 + cnt2 * (cnt2 - 1) / 2 + cnt1 * cnt3;
ans = max(ans, sum);
}
}
cout << ans << endl;
return 0;
}
/*
6
0 0
0 6
6 0
6 6
1 4
1 2
7
-2 0
0 -2
2 0
0 2
-1 -1
0 0
1 1
2
0 0
0 1
4
-3 0
3 0
0 3
0 1
4
0 0
0 1
1 0
1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3728kb
input:
6 0 0 0 6 6 0 6 6 1 4 1 2
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
2 0 0 0 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
4 -3 0 3 0 0 3 0 1
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
4 0 0 0 1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
2 0 -1337 -5 -4
output:
0
result:
ok single line: '0'
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3600kb
input:
1000 496963365 -584310020 963238159 -571008004 18078662 -750762438 135156509 -968440195 77520950 -725908810 956053561 -538228505 806742035 -803854232 529068738 -825479182 64371444 -975013392 164324947 -824966981 629969244 -744727107 685160229 -787078273 985061882 -907085223 349370979 -716383138 4759...
output:
0
result:
wrong answer 1st lines differ - expected: '248984', found: '0'