QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#456389 | #7131. Random points | propane | WA | 1ms | 3724kb | C++20 | 3.0kb | 2024-06-27 20:40:42 | 2024-06-27 20:40:42 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;
const int maxn = 2005, mod = 1e9 + 7;
void add(int &a, int b){
a += b;
if (a >= mod) a -= mod;
}
int sub(int a, int b){
a -= b;
if (a < 0) a += mod;
return a;
}
int mul(int a, int b){
return 1LL * a * b % mod;
}
int pow2[maxn];
struct Point{
LL x, y;
bool operator==(const Point &t) const {
return x == t.x and y == t.y;
}
Point operator-(const Point &t) const {
return {x - t.x, y - t.y};
}
LL operator*(const Point &t) const {
return x * t.x + y * t.y;
}
LL operator^(const Point &t) const {
return x * t.y - y * t.x;
}
int quad() const {
if (y < 0) return 1;
if (y > 0) return 4;
if (x > 0) return 2;
if (x < 0) return 5;
return 3;
}
bool operator<(const Point &t) const {
int q1 = quad(), q2 = t.quad();
if (q1 != q2) return q1 < q2;
return (*this ^ t) > 0;
}
};
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
pow2[0] = 1;
for(int i = 1; i < maxn; i++){
pow2[i] = mul(pow2[i - 1], 2);
}
int n;
cin >> n;
vector<Point> p(n);
for(int i = 0; i < n; i++){
cin >> p[i].x >> p[i].y;
}
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
int ans = 0;
// 枚举每个点,计算其出现但是不在凸包上的方案数
for(int i = 0; i < p.size(); i++){
vector<Point> q;
q.reserve(p.size());
for(auto pt : p){
if (pt != p[i]){
q.push_back(pt - p[i]);
}
}
sort(q.begin(), q.end());
auto check1 = [&](int x, int y){
LL t = q[x] ^ q[y];
if (t > 0) return true;
if (t < 0) return false;
return (q[x] * q[y]) > 0;
};
auto check2 = [&](int x, int y){
LL t = p[x] ^ p[y];
return t >= 0;
};
int sum = 0;
for(int i = 0, j = 0, k = 0; i < q.size(); i++){
j = max(j, i);
k = max(k, i);
while(j < q.size() and check1(i, j)) j++;
while(k < q.size() and check2(i, k)) k++;
int c1 = j - i - 1;
int c2 = k - j;
int c3 = int(q.size()) - k;
// 取正好形成平角的点,剩下的任取
add(sum, mul(sub(pow2[c2], 1), pow2[c1 + c3]));
// 不取形成平角的点,剩下的两种点必须都不为空集.
add(sum, mul(sub(pow2[c1], 1), sub(pow2[c3], 1)));
}
add(ans, sub(pow2[p.size() - 1], sum));
}
ans = mul(ans, pow2[n - p.size()]);
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3724kb
input:
3 0 0 0 1 1 0
output:
12
result:
ok 1 number(s): "12"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
3 0 0 0 1 0 2
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3600kb
input:
20 3 3 1 0 0 2 2 2 2 4 4 3 0 0 1 4 0 1 4 2 3 4 1 0 3 1 4 4 3 1 1 3 4 1 1 4 3 0 3 1
output:
4175328
result:
wrong answer 1st numbers differ - expected: '5996938', found: '4175328'