QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#836442 | #9924. Reconstruction | ucup-team6275# | WA | 0ms | 3804kb | C++17 | 3.9kb | 2024-12-28 20:46:59 | 2024-12-28 20:47:00 |
Judging History
answer
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
using namespace std;
#define ll long long
struct point {
ll x, y;
ll len2() {
return x * x + y * y;
}
};
bool operator<(point a, point b) {
return make_pair(a.x, a.y) < make_pair(b.x, b.y);
}
point operator-(point a, point b) {
return {a.x - b.x, a.y - b.y};
}
point operator+(point a, point b) {
return {a.x - b.x, a.y - b.y};
}
ll operator%(point a, point b) {
return a.x * b.y - a.y * b.x;
}
int sign(ll x) {
if (x > 0) return 1;
if (x == 0) return 0;
return -1;
}
vector<point> convexHull(vector<point> p) {
if (p.empty()) {
return {};
}
int n = p.size();
int pos = min_element(p.begin(), p.end()) - p.begin();
swap(p[0], p[pos]);
for (int i = 1; i < n; ++i)
p[i] = p[i] - p[0];
sort(p.begin() + 1, p.end(), [&](point &lhs, point &rhs) -> bool {
int sgn = sign(lhs % rhs);
if (!sgn) {
return lhs.len2() < rhs.len2();
}
return sgn == 1;
});
for (int i = 1; i < n; ++i)
p[i] = p[i] + p[0];
int top = 0;
for (int i = 0; i < n; ++i) {
while (top >= 2) {
point v1 = p[top - 1] - p[top - 2];
point v2 = p[i] - p[top - 1];
if (v1 % v2 > 0)
break;
--top;
}
p[top++] = p[i];
}
p.resize(top);
return p;
}
ll calc_sq(vector <point>& a) {
ll ans = 0;
int n = a.size();
for (int i = 1; i < n - 1; ++i) {
ans += (a[i] - a[0]) % (a[i + 1] - a[0]);
}
return abs(ans);
}
int half(point a) {
if (a.y > 0 || (a.y == 0 && a.x > 0)) return 0;
return 1;
}
bool cmp(point a, point b) {
int h1 = half(a);
int h2 = half(b);
if (h1 != h2) return h1 < h2;
return a % b > 0;
}
const ll mod = 1e9 + 7;
inline int mul(int a, int b) {
return 1ll * a * b % mod;
}
inline int power(int a, int pw) {
int ans = 1;
while (pw) {
if (pw & 1) {
ans = mul(ans, a);
}
a = mul(a, a);
pw >>= 1;
}
return ans;
}
inline int inv(int x) {
return power(x, mod - 2);
}
inline int add(int a, int b) {
a += b;
if (a >= mod) a -= mod;
return a;
}
inline int sub(int a, int b) {
a -= b;
if (a < 0) a += mod;
return a;
}
void solve() {
int n;
cin >> n;
vector <point> a(n);
for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y;
auto ch = convexHull(a);
map <pair <ll, ll>, int> isc;
for (auto i : ch) {
isc[make_pair(i.x, i.y)] = 1;
}
ll S = calc_sq(ch);
// int inv2 = inv(2);
int ln = ch.size();
vector <point> vecs;
int answer = 0;
for (auto i : a) {
if (isc.count(make_pair(i.x, i.y))) continue;
vector <int> banned(ln);
for (int j = 0; j < ch.size(); ++j) {
vecs.push_back(ch[j] - i);
}
sort(vecs.begin(), vecs.end(), cmp);
for (auto j : a) {
if (isc.count(make_pair(j.x, j.y)) || (i.x == j.x && i.y == j.y)) continue;
auto it = lower_bound(vecs.begin(), vecs.end(), j, cmp);
int kek = (it - vecs.begin()) % ln;
banned[kek] = 1;
}
for (int j = 0; j < ln; ++j) {
if (banned[j]) continue;
answer = add(answer, S);
int prv = (j - 1 + ln) % ln;
ll S2 = abs(vecs[prv] % vecs[j]);
S2 %= mod;
answer = sub(answer, S2);
}
}
cout << answer;
}
signed main() {
if (1) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
/*
4
0 0
2 0
1 2
1 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3804kb
input:
3 1 2 2 3 2 1 1 3
output:
1000000003
result:
wrong answer 1st lines differ - expected: '001', found: '1000000003'