QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#721429 | #5540. City Hall | zijinjun# | WA | 0ms | 3580kb | C++17 | 3.7kb | 2024-11-07 16:05:52 | 2024-11-07 16:05:53 |
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>;
struct Point {
int 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);
}
double Dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
double 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;
}
};
bool is_between(int x, int l, int r) {
return l <= x && x <= r;
}
int main() {
n = read();
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) % n] - 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 + 1);
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(0, 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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3580kb
input:
5 6 1 3 5 100 8 2 10 1 2 2 3 2 5 1 4 4 5 3 5
output:
2
result:
wrong answer 1st numbers differ - expected: '4.5000000', found: '2.0000000', error = '0.5555556'