| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 43754 | 2018-03-22T11:29:45 Z | chpipis | The Forest of Fangorn (CEOI14_fangorn) | C++11 | 1568 ms | 33708 KB |
#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 MAX_N = 2e3 + 5;
const int MAX_C = 1e4 + 5;
inline ll cross(ii a, ii b) {
return a.fi * 1LL * b.se - a.se * 1LL * b.fi;
}
bool comp(vii vec) {
for (int i = 0; i < 3; i++) {
int nxt = (i + 1) % 3;
int prv = (i + 3 - 1) % 3;
if (cross(vec[i], vec[nxt]) > 0 && cross(vec[prv], vec[i]) > 0)
return true;
}
return false;
}
ii tree[MAX_N], camp[MAX_C];
vii vec[MAX_N];
ii best[MAX_N][2];
int main() {
//freopen("", "r", stdin);
//freopen("", "w", stdout);
int w, h;
scanf("%d %d", &w, &h);
ii gimli;
scanf("%d %d", &gimli.fi, &gimli.se);
int c;
scanf("%d", &c);
for (int i = 1; i <= c; i++) {
scanf("%d %d", &camp[i].fi, &camp[i].se);
}
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &tree[i].fi, &tree[i].se);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) continue;
ii point = tree[j];
point.fi -= tree[i].fi;
point.se -= tree[i].se;
point.fi *= -1;
point.se *= -1;
vec[i].pb(point);
}
}
for (int i = 1; i <= n; i++) {
best[i][0] = best[i][1] = vec[i][0];
for (int j = 1; j < (int)vec[i].size(); j++) {
ii cur = vec[i][j];
ii gnow = gimli;
gnow.fi -= tree[i].fi;
gnow.se -= tree[i].se;
if (comp((vii){gnow, best[i][0], cur}))
best[i][0] = cur;
if (comp((vii){gnow, cur, best[i][1]}))
best[i][1] = cur;
}
}
vi ans;
for (int i = 1; i <= c; i++) {
bool found = true;
for (int j = 1; j <= n; j++) {
ii cur = camp[i];
cur.fi -= tree[j].fi;
cur.se -= tree[j].se;
if (!comp((vii){best[j][0], cur, best[j][1]}))
found = false;
}
if (found) ans.pb(i);
}
printf("%d\n", (int)ans.size());
for (auto it : ans)
printf("%d ", it);
puts("");
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 508 KB | Output is correct |
| 2 | Correct | 1 ms | 508 KB | Output is correct |
| 3 | Correct | 1 ms | 592 KB | Output is correct |
| 4 | Correct | 1 ms | 700 KB | Output is correct |
| 5 | Correct | 1 ms | 700 KB | Output is correct |
| 6 | Correct | 1 ms | 756 KB | Output is correct |
| 7 | Correct | 2 ms | 848 KB | Output is correct |
| 8 | Correct | 2 ms | 856 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 856 KB | Output is correct |
| 2 | Correct | 2 ms | 856 KB | Output is correct |
| 3 | Correct | 2 ms | 884 KB | Output is correct |
| 4 | Correct | 2 ms | 888 KB | Output is correct |
| 5 | Correct | 3 ms | 892 KB | Output is correct |
| 6 | Correct | 4 ms | 1024 KB | Output is correct |
| 7 | Correct | 1 ms | 1024 KB | Output is correct |
| 8 | Correct | 2 ms | 1024 KB | Output is correct |
| 9 | Correct | 2 ms | 1024 KB | Output is correct |
| 10 | Correct | 6 ms | 1168 KB | Output is correct |
| 11 | Correct | 9 ms | 1172 KB | Output is correct |
| 12 | Correct | 9 ms | 1308 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 1308 KB | Output is correct |
| 2 | Correct | 2 ms | 1308 KB | Output is correct |
| 3 | Correct | 2 ms | 1308 KB | Output is correct |
| 4 | Correct | 131 ms | 8976 KB | Output is correct |
| 5 | Correct | 30 ms | 8976 KB | Output is correct |
| 6 | Correct | 506 ms | 33108 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 656 ms | 33400 KB | Output is correct |
| 2 | Correct | 1265 ms | 33520 KB | Output is correct |
| 3 | Correct | 1568 ms | 33660 KB | Output is correct |
| 4 | Correct | 1474 ms | 33708 KB | Output is correct |