Submission #57461902
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pl = array<ll, 2>;
constexpr ll INF = 1e12 + 7;
constexpr ll mod = 1e9 + 7;
constexpr ld eps = 1e-9;
const ld PI = acos(-1);
struct Point {
int64_t x, y;
Point(int64_t x_, int64_t y_) : x(x_), y(y_) {}
Point operator-(const Point &p) const {
return Point(x - p.x, y - p.y);
}
int64_t cross(const Point &p) const {
return x * p.y - y * p.x;
}
int64_t cross(const Point &p, const Point &q) const {
return (p - *this).cross(q - *this);
}
int half() const {
return int(y < 0 || (y == 0 && x < 0));
}
};
std::vector<std::vector<size_t>> find_faces(std::vector<Point> vertices, std::vector<std::vector<int>> adj) {
size_t n = vertices.size();
std::vector<std::vector<char>> used(n);
for (size_t i = 0; i < n; i++) {
used[i].resize(adj[i].size());
used[i].assign(adj[i].size(), 0);
auto compare = [&](size_t l, size_t r) {
Point pl = vertices[l] - vertices[i];
Point pr = vertices[r] - vertices[i];
if (pl.half() != pr.half())
return pl.half() < pr.half();
return pl.cross(pr) > 0;
};
std::sort(adj[i].begin(), adj[i].end(), compare);
}
std::vector<std::vector<size_t>> faces;
for (size_t i = 0; i < n; i++) {
for (size_t edge_id = 0; edge_id < adj[i].size(); edge_id++) {
if (used[i][edge_id]) {
continue;
}
std::vector<size_t> face;
size_t v = i;
size_t e = edge_id;
while (!used[v][e]) {
used[v][e] = true;
face.push_back(v);
size_t u = adj[v][e];
size_t e1 = std::lower_bound(adj[u].begin(), adj[u].end(), v, [&](size_t l, size_t r) {
Point pl = vertices[l] - vertices[u];
Point pr = vertices[r] - vertices[u];
if (pl.half() != pr.half())
return pl.half() < pr.half();
return pl.cross(pr) > 0;
}) - adj[u].begin() + 1;
if (e1 == adj[u].size()) {
e1 = 0;
}
v = u;
e = e1;
}
std::reverse(face.begin(), face.end());
int sign = 0;
for (size_t j = 0; j < face.size(); j++) {
size_t j1 = (j + 1) % face.size();
size_t j2 = (j + 2) % face.size();
int64_t val = vertices[face[j]].cross(vertices[face[j1]], vertices[face[j2]]);
if (val > 0) {
sign = 1;
break;
} else if (val < 0) {
sign = -1;
break;
}
}
if (sign <= 0) {
faces.insert(faces.begin(), face);
} else {
faces.emplace_back(face);
}
}
}
return faces;
}
vector<int> p;
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
void unite(int x, int y) {
x = find(x), y = find(y);
if (x != y)p[x] = y;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
ll n;
cin >> n;
if (!n)return cout << 0, 0;
p.resize(n);
iota(p.begin(), p.end(), 0);
vector<pl> a(n);
map<pl, int> who;
for (auto &[x, y]: a)cin >> x >> y;
for (int i = 0; i < n; ++i) {
who[a[i]] = i;
}
vector<vector<int>> g(n);
for (int i = 0; i < n; ++i) {
for (int dx = -1; dx <= 1; ++dx) {
for (int dy = -1; dy <= 1; ++dy) {
if (!dx && !dy)continue;
auto to = pl{a[i][0] + dx, a[i][1] + dy};
if (who.count(to)) {
if (dx && dy && who.count(pl{a[i][0] + dx, a[i][1]}) &&
who.count(pl{a[i][0], a[i][1] + dy}))
continue;
g[i].push_back(who[to]);
unite(i, who[to]);
}
}
}
}
map<ll, vector<pl>> X, Y;
ll res = 0;
vector<vector<int>> all(n);
for (int v = 0; v < n; ++v)all[find(v)].push_back(v);
for (int v = 0; v < n; ++v) {
if (all[v].empty())continue;
sort(all[v].begin(), all[v].end());
vector<Point> vertices;
vector<vector<int>> E(all[v].size());
for (auto i: all[v])vertices.emplace_back(a[i][0], a[i][1]);
for (int i = 0; i < all[v].size(); ++i) {
for (auto to: g[all[v][i]]) {
int pos = lower_bound(all[v].begin(), all[v].end(), to) - all[v].begin();
E[i].push_back(pos);
}
}
auto c = find_faces(vertices, E);
c.erase(c.begin());
for (auto &q: c) {
for (auto id: q) {
int i = all[v][id];
X[a[i][0]].push_back({a[i][1], i});
Y[a[i][1]].push_back({a[i][0], i});
}
}
}
for (auto &[_, v]: X)sort(v.begin(), v.end());
for (auto &[_, v]: Y)sort(v.begin(), v.end());
vector<char> bad(n, 0);
for (int v = 0; v < n; ++v) {
if (all[v].empty())continue;
set<int> l, r, u, d;
for (auto id: all[v]) {
auto [x, y] = a[id];
{
auto it = lower_bound(X[x].begin(), X[x].end(), pl{y, INF});
if (it != X[x].end()) {
auto [_, what] = *it;
int q = find(what);
if (v != q) {
r.insert(q);
}
}
it = upper_bound(X[x].begin(), X[x].end(), pl{y, -1});
if (it != X[x].begin()) {
auto [_, what] = *(--it);
int q = find(what);
if (v != q) {
l.insert(q);
}
}
}
{
auto it = lower_bound(Y[y].begin(), Y[y].end(), pl{x, INF});
if (it != Y[y].end()) {
auto [_, what] = *it;
int q = find(what);
if (v != q) {
u.insert(q);
}
}
it = upper_bound(Y[y].begin(), Y[y].end(), pl{x, -1});
if (it != Y[y].begin()) {
auto [_, what] = *(--it);
int q = find(what);
if (v != q) {
d.insert(q);
}
}
}
}
}
for (ll v = 0; v < n; ++v) {
if (bad[find(v)])--res;
}
for (int v = 0; v < n; ++v) {
if (all[v].empty())continue;
if (bad[find(all[v].front())])continue;
sort(all[v].begin(), all[v].end());
vector<Point> vertices;
vector<vector<int>> E(all[v].size());
for (auto i: all[v])vertices.emplace_back(a[i][0], a[i][1]);
for (int i = 0; i < all[v].size(); ++i) {
for (auto to: g[all[v][i]]) {
int pos = lower_bound(all[v].begin(), all[v].end(), to) - all[v].begin();
E[i].push_back(pos);
}
}
auto c = find_faces(vertices, E);
c.erase(c.begin());
for (auto &q: c) {
for (auto &id: q)id = all[v][id];
}
for (auto &v: c) {
ll S = 0;
ll n = v.size();
for (int i = 0; i < n; ++i) {
S += (a[v[(i + 1) % n]][0] - a[v[i]][0]) * (a[v[(i + 1) % n]][1] + a[v[i]][1]);
}
S = abs(S);
ll inside = (S + 2 - n) / 2;
res += inside;
}
}
cout << res;
}
Submission Info
Submission Time
2024-09-06 02:57:57+0900
Task
G - Go Territory
User
ZergTricky
Language
C++ 20 (gcc 12.2)
Score
0
Code Size
8089 Byte
Status
RE
Exec Time
921 ms
Memory
122140 KiB
Compile Error
Main.cpp: In function ‘int main()’:
Main.cpp:148:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
148 | for (int i = 0; i < all[v].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
Main.cpp:220:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
220 | for (int i = 0; i < all[v].size(); ++i) {
| ~~^~~~~~~~~~~~~~~
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
0 / 600
Status
Set Name
Test Cases
Sample
sample_01.txt, sample_02.txt, sample_03.txt
All
random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt
Case Name
Status
Exec Time
Memory
random_01.txt
WA 531 ms
46968 KiB
random_02.txt
WA 539 ms
46884 KiB
random_03.txt
WA 533 ms
46928 KiB
random_04.txt
WA 655 ms
59200 KiB
random_05.txt
WA 654 ms
58612 KiB
random_06.txt
WA 654 ms
58428 KiB
random_07.txt
WA 697 ms
61468 KiB
random_08.txt
RE 549 ms
61224 KiB
random_09.txt
AC 704 ms
105976 KiB
random_10.txt
AC 695 ms
106028 KiB
random_11.txt
RE 317 ms
36584 KiB
random_12.txt
RE 383 ms
36656 KiB
random_13.txt
RE 436 ms
36572 KiB
random_14.txt
RE 473 ms
37324 KiB
random_15.txt
WA 921 ms
122140 KiB
random_16.txt
AC 429 ms
85148 KiB
random_17.txt
AC 518 ms
101080 KiB
random_18.txt
RE 260 ms
35228 KiB
random_19.txt
RE 259 ms
35268 KiB
random_20.txt
RE 260 ms
35272 KiB
sample_01.txt
AC 1 ms
3644 KiB
sample_02.txt
AC 1 ms
3428 KiB
sample_03.txt
AC 1 ms
3564 KiB
test_00.txt
RE 109 ms
5528 KiB
test_01.txt
WA 55 ms
7224 KiB
test_02.txt
WA 24 ms
5700 KiB
test_03.txt
WA 72 ms
9272 KiB
test_04.txt
RE 80 ms
3816 KiB