#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)
// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif
#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
advance(it, -n);
return it;
}
template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
advance(it, n);
return it;
}
#endif
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;
const double EPS = 1e-9;
const double PI = 3.141592653589793238462;
template<typename T>
inline T sq(T a) { return a * a; }
//#ifdef LOCAL_MACHINE
//#endif
const int MAXN = 1e5 + 5;
inline ll ccw(ii a, ii b, ii c) {
return (b.fi - a.fi) * 1LL * (c.se - a.se) - (b.se - a.se) * 1LL * (c.fi - a.fi);
}
struct comp {
inline bool operator() (ii lhs, ii rhs) {
return ccw(ii(0, 0), lhs, rhs) > 0;
}
};
ii pts[MAXN];
multiset<ii, comp> active;
int main() {
//freopen("", "r", stdin);
//freopen("", "w", stdout);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d %d", &pts[i].fi, &pts[i].se);
active.insert(pts[i]);
}
for (int i = 0; i < n; i++) {
ii a = pts[i], b = pts[(i + 1) % n];
if (ccw(ii(0, 0), a, b) < 0) swap(a, b);
auto st = active.lower_bound(a);
auto en = active.upper_bound(b);
while (st != en) {
if (*st != a && *st != b && ccw(a, *st, b) > 0)
st = active.erase(st);
else
st++;
}
}
printf("%d\n", (int)active.size());
vii vec(all(active));
sort(all(vec));
for (int i = 0; i < n; i++) {
auto it = lower_bound(all(vec), pts[i]);
if (it != vec.end() && *it == pts[i])
printf("%d ", i + 1);
}
puts("");
return 0;
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
circuit.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &pts[i].fi, &pts[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
484 KB |
Output is correct |
| 3 |
Correct |
6 ms |
580 KB |
Output is correct |
| 4 |
Correct |
5 ms |
772 KB |
Output is correct |
| 5 |
Correct |
57 ms |
948 KB |
Output is correct |
| 6 |
Correct |
50 ms |
1044 KB |
Output is correct |
| 7 |
Execution timed out |
251 ms |
1560 KB |
Time limit exceeded |
| 8 |
Correct |
37 ms |
1560 KB |
Output is correct |
| 9 |
Execution timed out |
120 ms |
1560 KB |
Time limit exceeded |
| 10 |
Correct |
61 ms |
1560 KB |
Output is correct |
| 11 |
Correct |
66 ms |
1560 KB |
Output is correct |
| 12 |
Correct |
14 ms |
1576 KB |
Output is correct |
| 13 |
Execution timed out |
740 ms |
2216 KB |
Time limit exceeded |
| 14 |
Correct |
26 ms |
2764 KB |
Output is correct |
| 15 |
Correct |
34 ms |
3240 KB |
Output is correct |
| 16 |
Correct |
60 ms |
5996 KB |
Output is correct |
| 17 |
Execution timed out |
1060 ms |
5996 KB |
Time limit exceeded |
| 18 |
Execution timed out |
51 ms |
6056 KB |
Time limit exceeded (wall clock) |
| 19 |
Execution timed out |
57 ms |
6056 KB |
Time limit exceeded (wall clock) |
| 20 |
Execution timed out |
108 ms |
6056 KB |
Time limit exceeded (wall clock) |
