#include <bits/stdc++.h>
const int MAX_N = 100000;
struct Fraction {
int a, b;
Fraction() {
a = 0;
b = 1;
}
Fraction(int _a, int _b) {
a = _a;
b = _b;
if(b < 0) {
a = -a;
b = -b;
}
}
bool operator== (const Fraction x) const {
return (long long)a * x.b == (long long)b * x.a;
}
bool operator< (const Fraction x) const {
return (long long)a * x.b < b * x.a;
}
};
struct Point {
int x, y;
Fraction slope;
} points[MAX_N];
bool marked[MAX_N];
static inline long long detarea(int a, int b) {
return (long long)points[a].x * points[b].y - (long long)points[a].y * points[b].x;
}
static inline long long quadarea(int a, int b, int c, int d) {
return detarea(a, b) + detarea(b, c) + detarea(c, d) + detarea(d, a);
}
static inline long long triarea(int a, int b, int c) {
return detarea(a, b) + detarea(b, c) + detarea(c, a);
}
struct Segment {
int a, b;
bool operator< (const Segment x) const {
if(b == x.a)
return true;
if(a == x.b)
return false;
long long area = quadarea(a, b, x.b, x.a);
if(area == 0)
return points[a].x < points[x.a].x;
return area < 0;
}
} segments[MAX_N];
struct Event {
Fraction t;
int type, segmentId;
};
bool cmp(Event a, Event b) {
return a.t < b.t || (a.t == b.t && a.type < b.type);
}
int main() {
int N;
scanf("%d", &N);
for(int i = 0; i < N; ++i) {
scanf("%d%d", &points[i].x, &points[i].y);
points[i].slope = Fraction(points[i].y, points[i].x);
segments[i] = {i, (i + 1) % N};
}
std::vector<Event> ev;
for(int i = 0; i < N; ++i) {
if(points[segments[i].b].slope < points[segments[i].a].slope)
std::swap(segments[i].a, segments[i].b);
else if(points[segments[i].b].slope == points[segments[i].a].slope &&
points[segments[i].b].x > points[segments[i].a].x)
std::swap(segments[i].a, segments[i].b);
ev.push_back({points[segments[i].a].slope, 0, i});
ev.push_back({points[segments[i].b].slope, 2, i});
ev.push_back({points[i].slope, 1, i});
}
std::sort(ev.begin(), ev.end(), cmp);
std::set<Segment> segs;
for(int i = 0; i < 3 * N; ++i) {
//printf("Event: %d %d-%d\n", ev[i].type,
// segments[ev[i].segmentId].a + 1,
// segments[ev[i].segmentId].b + 1);
if(ev[i].type == 0) {
segs.insert(segments[ev[i].segmentId]);
} else if(ev[i].type == 2)
segs.erase(segments[ev[i].segmentId]);
else {
Segment firstseg = *segs.begin();
if(points[firstseg.a].slope == points[firstseg.b].slope)
marked[ev[i].segmentId] = (ev[i].segmentId == firstseg.a);
else
marked[ev[i].segmentId] = (ev[i].segmentId == firstseg.a ||
ev[i].segmentId == firstseg.b);
}
//printf("Debug segments:\n");
//for(auto it: segs) {
// printf("[%d %d]\n", it.a + 1, it.b + 1);
//}
}
//printf("??%d %d\n", segments[2] < segments[3], segments[3] < segments[2]);
//printf("%lld\n", quadarea(segments[2].a, segments[2].b, segments[3].b, segments[3].a));
//printf("%lld\n", quadarea(segments[2].a, segments[2].b, segments[3].a, segments[3].b));
int res = 0;
for(int i = 0; i < N; ++i)
if(marked[i])
++res;
printf("%d\n", res);
for(int i = 0; i < N; ++i)
if(marked[i])
printf("%d ", i + 1);
return 0;
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
circuit.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &points[i].x, &points[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1920 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2304 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
2936 KB |
Output isn't correct |
| 6 |
Incorrect |
14 ms |
2936 KB |
Output isn't correct |
| 7 |
Incorrect |
22 ms |
3448 KB |
Output isn't correct |
| 8 |
Incorrect |
9 ms |
2808 KB |
Output isn't correct |
| 9 |
Correct |
11 ms |
2684 KB |
Output is correct |
| 10 |
Incorrect |
11 ms |
2936 KB |
Output isn't correct |
| 11 |
Incorrect |
12 ms |
3320 KB |
Output isn't correct |
| 12 |
Correct |
20 ms |
3448 KB |
Output is correct |
| 13 |
Incorrect |
36 ms |
4840 KB |
Output isn't correct |
| 14 |
Correct |
45 ms |
4852 KB |
Output is correct |
| 15 |
Correct |
50 ms |
7152 KB |
Output is correct |
| 16 |
Execution timed out |
111 ms |
12244 KB |
Time limit exceeded |
| 17 |
Execution timed out |
125 ms |
12388 KB |
Time limit exceeded |
| 18 |
Execution timed out |
33 ms |
4088 KB |
Time limit exceeded (wall clock) |
| 19 |
Execution timed out |
33 ms |
4088 KB |
Time limit exceeded (wall clock) |
| 20 |
Execution timed out |
31 ms |
4224 KB |
Time limit exceeded (wall clock) |
