#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;
}
bool operator!= (const Fraction x) const {
return !(*this == x);
}
};
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;
Fraction last_slope;
int best_point = -1;
// I feel like Yandere-dev
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) {
if(points[segments[ev[i].segmentId].a].slope == // Am un segment cu aceleasi pante la origine
points[segments[ev[i].segmentId].b].slope) {
if(points[segments[ev[i].segmentId].a].slope == last_slope) { // last_slope e updatat
if(points[segments[ev[i].segmentId].a].x < points[best_point].x) { // vad punctul cel mai
// aproape de origine
best_point = segments[ev[i].segmentId].a;
}
} else {
last_slope = points[segments[ev[i].segmentId].a].slope;
best_point = segments[ev[i].segmentId].a;
}
} else {
segs.insert(segments[ev[i].segmentId]);
}
} else if(ev[i].type == 2) {
if(points[segments[ev[i].segmentId].a].slope !=
points[segments[ev[i].segmentId].b].slope)
segs.erase(segments[ev[i].segmentId]);
} else {
if(segs.empty()) {
marked[best_point] = true;
} else {
Segment firstseg = *segs.begin();
if(last_slope != ev[i].t) {
last_slope = ev[i].t;
best_point = -1;
}
if(points[firstseg.a].slope == last_slope &&
(best_point == -1 || (best_point != -1 && points[firstseg.a].x < points[best_point].x)))
best_point = firstseg.a;
if(points[firstseg.b].slope == last_slope &&
(best_point == -1 || (best_point != -1 && points[firstseg.b].x < points[best_point].x)))
best_point = firstseg.b;
if(best_point != -1)
marked[best_point] = true;
}
}
//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:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
circuit.cpp:81: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 |
Incorrect |
1 ms |
1920 KB |
Output isn't correct |
| 2 |
Correct |
3 ms |
2048 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
6 ms |
2304 KB |
Output is correct |
| 5 |
Incorrect |
11 ms |
2808 KB |
Output isn't correct |
| 6 |
Incorrect |
11 ms |
2808 KB |
Output isn't correct |
| 7 |
Incorrect |
19 ms |
3192 KB |
Output isn't correct |
| 8 |
Incorrect |
9 ms |
2680 KB |
Output isn't correct |
| 9 |
Correct |
10 ms |
2680 KB |
Output is correct |
| 10 |
Incorrect |
11 ms |
2680 KB |
Output isn't correct |
| 11 |
Incorrect |
13 ms |
3192 KB |
Output isn't correct |
| 12 |
Correct |
20 ms |
3192 KB |
Output is correct |
| 13 |
Incorrect |
33 ms |
4452 KB |
Output isn't correct |
| 14 |
Correct |
42 ms |
4340 KB |
Output is correct |
| 15 |
Correct |
50 ms |
6512 KB |
Output is correct |
| 16 |
Execution timed out |
121 ms |
10980 KB |
Time limit exceeded |
| 17 |
Execution timed out |
126 ms |
11108 KB |
Time limit exceeded |
| 18 |
Execution timed out |
25 ms |
2688 KB |
Time limit exceeded (wall clock) |
| 19 |
Execution timed out |
24 ms |
2680 KB |
Time limit exceeded (wall clock) |
| 20 |
Execution timed out |
28 ms |
2680 KB |
Time limit exceeded (wall clock) |
