QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#234656 | #5538. Magical Barrier | dmmm# | WA | 1ms | 3728kb | C++20 | 2.5kb | 2023-11-01 20:27:36 | 2023-11-01 20:27:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 7;
typedef struct Vector {
int x,y;
int id;
Vector operator - (Vector &oth) {
return {x - oth.x , y - oth.y};
}
int dot (Vector &oth) {
return oth.x * x + y * oth.y;
}
int cross (Vector &oth) {
return oth.y * x - y * oth.x;
}
bool operator < (const Vector&oth) const {
return x < oth.x || (x==oth.x && y < oth.y);
}
} point;
bool ban[N];
point dick;
int direc (point a,point b,point c) {
Vector x = b - a;
Vector y = c - b;
return x.cross (y);
}
bool ccw (point a,point b,point c) {
return direc (a , b, c) > 0;
}
bool cw (point a,point b,point c) {
return direc (a , b , c) < 0;
}
void convex_hull (vector<point> &a) {
sort (a .begin() ,a .end());
vector<point> up , down;
point first = a[0] , last = a.back();
up.push_back (first);
down.push_back (first);
dick = first;
int p = a.size() - 1;
for (int i=1;i<(int ) a.size();i++) {
if (i==p || cw (first , a[i] , last)) {
while (up.size() >=2 && !cw (up[(int) up.size() - 2] , up.back() , a[i])) up.pop_back ();
up.push_back (a[i]);
}
if (i==p || ccw (first , a[i] , last)) {
while (down.size() >=2 && !ccw (down[(int) down.size() - 2] , down.back() , a[i])) down.pop_back ();
down.push_back (a[i]);
}
}
a.clear();
for (point &i : up) {
a.push_back (i);
ban[i.id] = 1;
}
for (int i=(int) down.size() - 2;i >= 1;i--) {
a.push_back (down[i]);
ban[down[i].id] = 1;
}
}
int n;
point a[N];
vector<point> b;
point x[N * 2];
int cal (int l, int r) {
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++) {
if (i==x[l].id || i==x[r].id) {
continue;
}
if (ccw (x[l], a[i], x[r])) {
cnt1++;
}
else {
cnt2++;
}
}
return cnt1 * cnt2;
}
signed main () {
ios::sync_with_stdio (false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
a[i].id = i;
b.push_back (a[i]);
}
if (n <= 2) {
cout << 0;
return 0;
}
convex_hull (b);
for (int i = 0; i < (int) b.size(); i++) {
x[i] = x[i + (int)b.size()] = b[i];
}
int res = 0;
int op = 1;
int m = b.size();
// cout << m << endl;
for (int i = 0; i < m; i++) {
for (int j = op; j < m + i; j++) {
if (j == m + i - 1) {
op = m + i - 1;
break;
}
else if (cal (i, j) > cal (i, j + 1)){
op = j;
break;
}
}
res = max (res, cal (i, op));
}
cout << res;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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: 3648kb
input:
2 0 0 0 1
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3668kb
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: 3664kb
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: 3592kb
input:
2 0 -1337 -5 -4
output:
0
result:
ok single line: '0'
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3728kb
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'