#include <bits/stdc++.h>
using namespace std;
#define ii pair<int, int>
#define f first
#define s second
struct Wall {
int a, b;
int idx;
bool operator<(const Wall &other) const {
if (a == other.a) return b < other.b;
return a < other.a;
}
};
int n;
ii A[100000];
vector<int> graph[100000];
vector<Wall> walls;
set<Wall> sortedWalls;
bool vis[200000][2];
bool done[200000];
vector<int> justDone;
int cross(int a, int b, int c) {
int w = A[b].f-A[a].f, x = A[b].s - A[a].s, y = A[c].f - A[b].f, z = A[c].s - A[b].s;
int cross = w*z-x*y;
return cross;
}
bool turnRight(int a, int b, int c) {
return cross(a, b, c) < 0;
}
bool turnLeft(int a, int b, int c) {
return cross(a, b, c) > 0;
}
bool goForward(int a, int b, int c) {
int w = A[b].f-A[a].f, x = A[b].s - A[a].s, y = A[c].f - A[b].f, z = A[c].s - A[b].s;
return (w==y&&(x<0)==(z<0))||(x==z&&(w<0)==(y<0));
return (A[a].f==A[b].f&&A[b].f==A[c].f&&(A[a].s<A[b].s&&A[b].s<A[c].s||A[a].s>A[b].s&&A[b].s>A[c].s))||(A[a].s==A[b].s&&A[b].s==A[c].s&&(A[a].f<A[b].f&&A[b].f<A[c].f||A[a].f>A[b].f&&A[b].f>A[c].f));
}
void go(int u, int dir) {
//cout << "go: " << u << " " << dir << endl;
if (vis[u][dir]) return;
vis[u][dir] = true;
justDone.push_back(u);
Wall w = walls[u];
sortedWalls.erase(w);
int prvNode = dir == 0 ? w.b : w.a;
int node = dir == 0 ? w.a : w.b;
// left
for (int wID : graph[node]) {
int nxtNode = walls[wID].a == node ? walls[wID].b : walls[wID].a;
int nxtDir = walls[wID].a == nxtNode ? 0 : 1;
if (!done[wID] && turnLeft(prvNode, node, nxtNode)) {
//cout << "left" << endl;
return go(wID, nxtDir);
}
}
// forward
for (int wID : graph[node]) {
int nxtNode = walls[wID].a == node ? walls[wID].b : walls[wID].a;
int nxtDir = walls[wID].a == nxtNode ? 0 : 1;
if (!done[wID] && goForward(prvNode, node, nxtNode)) {
//cout << "forward" << endl;
return go(wID, nxtDir);
}
}
// right
for (int wID : graph[node]) {
int nxtNode = walls[wID].a == node ? walls[wID].b : walls[wID].a;
int nxtDir = walls[wID].a == nxtNode ? 0 : 1;
if (!done[wID] && turnRight(prvNode, node, nxtNode)) {
//cout << "right" << endl;
return go(wID, nxtDir);
}
}
// back
for (int wID : graph[node]) {
int nxtNode = walls[wID].a == node ? walls[wID].b : walls[wID].a;
int nxtDir = walls[wID].a == nxtNode ? 0 : 1;
if (!done[wID]) {
//cout << "back" << endl;
return go(wID, nxtDir);
}
}
}
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> A[i].f >> A[i].s;
int w; cin >> w;
for (int i = 0; i < w; i++) {
int a, b; cin >> a >> b; --a; --b;
sortedWalls.insert({a,b,i});
walls.push_back({a,b,i});
graph[a].push_back(i);
graph[b].push_back(i);
vis[i][0] = vis[i][1] = false;
done[i] = false;
}
while (!sortedWalls.empty()) {
//cout << "=== new go ===" << endl;
int u = sortedWalls.begin()->idx;
int x = A[walls[u].a].f - A[walls[u].b].f, y = A[walls[u].b].s - A[walls[u].a].s;
if (x<0||y<0) {
go(sortedWalls.begin()->idx, 0);
} else {
go(sortedWalls.begin()->idx, 1);
}
for (int x : justDone) done[x] = true;
justDone.clear();
}
vector<int> ans;
for (int i = 0; i < w; i++) {
if (vis[i][0] && vis[i][1]) {
ans.push_back(i);
}
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); i++) {
cout << ans[i]+1 << endl;
}
return 0;
}
Compilation message
flood.cpp: In function 'bool goForward(int, int, int)':
flood.cpp:43:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
return (A[a].f==A[b].f&&A[b].f==A[c].f&&(A[a].s<A[b].s&&A[b].s<A[c].s||A[a].s>A[b].s&&A[b].s>A[c].s))||(A[a].s==A[b].s&&A[b].s==A[c].s&&(A[a].f<A[b].f&&A[b].f<A[c].f||A[a].f>A[b].f&&A[b].f>A[c].f));
^
flood.cpp:43:155: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
return (A[a].f==A[b].f&&A[b].f==A[c].f&&(A[a].s<A[b].s&&A[b].s<A[c].s||A[a].s>A[b].s&&A[b].s>A[c].s))||(A[a].s==A[b].s&&A[b].s==A[c].s&&(A[a].f<A[b].f&&A[b].f<A[c].f||A[a].f>A[b].f&&A[b].f>A[c].f));
^
flood.cpp: In function 'int main()':
flood.cpp:133:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ans.size(); i++) {
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 2 |
Correct |
7 ms |
2816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
2688 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
2688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
5320 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
247 ms |
17772 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
220 ms |
13096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
608 ms |
17856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
655 ms |
19412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
