| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 104425 |
2019-04-06T18:34:14 Z |
KiKoS |
Relay (COI16_relay) |
C++17 |
|
2000 ms |
2688 KB |
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#ifdef DEBUG
const int MAXN = 10;
const int MAXLOG = 4;
const int MAXSQRT = 4;
#else
const int MAXN = 3e5;
const int MAXLOG = 20;
const int MAXSQRT = 400;
#define cerr if (false) cerr
#endif
mt19937 rng(time(0));
#define int ll
const int INF = 1e9;
const int MOD = 1e9 + 7;
struct V {
int x, y;
V() {
}
V(int a, int b) {
x = a, y = b;
}
};
V operator + (V a, V b) {
return V(a.x + b.x, a.y + b.y);
}
V operator - (V a, V b) {
return V(a.x - b.x, a.y - b.y);
}
int operator ^ (V a, V b) {
return a.x * b.y - a.y * b.x;
}
int operator * (V a, V b) {
return a.x * b.x + a.y * b.y;
}
istream & operator >> (istream &in, V &a) {
in >> a.x >> a.y;
return in;
}
ostream & operator << (ostream &out, V a) {
out << a.x << ' ' << a.y;
return out;
}
int n, m;
V polygon[MAXN];
V dots[MAXN];
int dist[MAXN];
int D(V a, V b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool check(V a, V b) {
cerr << "check " << a << '\t' << b << '\n';
int pos_1 = -1;
int pos_2 = -1;
{
cerr << "pos_1\n";
int l = 0;
int r = n;
while (l + 1 < r) {
cerr << l << ' ' << r << '\n';
int mid = (l + r) >> 1;
if (((polygon[mid] - a) ^ (polygon[0] - a)) < 0) {
l = mid;
continue;
}
cerr << "here\n";
if (((polygon[mid] - a) ^ (polygon[(mid + 1) % n] - polygon[mid])) >= 0) {
r = mid;
}
else {
l = mid;
}
}
for (int i = 0; i < min(n, 5ll); i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = polygon[i] - a;
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_1 = i;
}
}
for (int i = max(0ll, r - 5); i < min(n, r + 6); i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = polygon[i] - a;
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_1 = i;
}
}
for (int i = max(0ll, n - 5); i < n; i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = polygon[i] - a;
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_1 = i;
}
}
for (int i = 0; i < min(n, 5ll); i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = a - polygon[i];
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_2 = i;
}
}
for (int i = max(0ll, r - 5); i < min(n, r + 6); i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = a - polygon[i];
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_2 = i;
}
}
for (int i = max(0ll, n - 5); i < n; i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = a - polygon[i];
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_2 = i;
}
}
}
{
int l = 0;
int r = n;
cerr << "pos_2\n";
while (l + 1 < r) {
cerr << l << ' ' << r << '\n';
int mid = (l + r) >> 1;
if (((polygon[mid] - a) ^ (polygon[0] - a)) > 0) {
r = mid;
continue;
}
if (((a - polygon[mid]) ^ (polygon[(mid + 1) % n] - polygon[mid])) >= 0) {
l = mid;
}
else {
r = mid;
}
}
for (int i = 0; i < min(n, 5ll); i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = a - polygon[i];
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_2 = i;
}
}
for (int i = max(0ll, r - 5); i < min(n, r + 6); i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = a - polygon[i];
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_2 = i;
}
}
for (int i = max(0ll, n - 5); i < n; i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = a - polygon[i];
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_2 = i;
}
}
for (int i = 0; i < min(n, 5ll); i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = polygon[i] - a;
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_1 = i;
}
}
for (int i = max(0ll, r - 5); i < min(n, r + 6); i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = polygon[i] - a;
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_1 = i;
}
}
for (int i = max(0ll, n - 5); i < n; i++) {
V A = polygon[(i + 1) % n] - polygon[i];
V B = polygon[i] - polygon[(i + n - 1) % n];
V C = polygon[i] - a;
bool _a = (C ^ A) >= 0;
bool _b = (B ^ C) >= 0;
bool _c = (A * C) > 0;
cerr << i << ' ' << _a << ' ' << _b << ' ' << _c << '\n';
if (_a && _b){// && _c) {
pos_1 = i;
}
}
}
int idx = 0;
while (pos_1 < 0 || pos_2 < 0) {
cerr << "u were keked\n";
idx += idx | idx + 1;
}
if (idx) {
cout << idx << '\n';
}
assert(pos_1 != -1);
assert(pos_2 != -1);
cerr << pos_1 << ' ' << pos_2 << '\n';
{
V A = polygon[pos_2] - a;
V B = polygon[pos_1] - a;
V C = b - a;
bool _a = (C ^ A) > 0;
bool _b = (B ^ C) > 0;
bool _c = (A * C) > 0;
cerr << _a << ' ' << _b << '\n';
if (!_a || !_b) {
return 1;
}
}
return 0;
// int l = 0;
// int r = n - 1;
// while (l + 1 < r) {
// int mid = (l + r)
// }
// int pos_1 = l;
}
inline void init() {
for (int i = 0; i < MAXN; i++) {
dist[i] = INF;
}
}
inline void solve() {
init();
for (int i = 0; i < m; i++) {
cin >> dots[i];
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> polygon[i];
}
queue<int> q;
q.push(0);
dist[0] = 0;
while (q.size()) {
int v = q.front();
q.pop();
for (int i = 1; i < m; i++) {
if (dist[i] != INF) {
continue;
}
if (check(dots[v], dots[i]) || check(dots[i], dots[v])) {
dist[i] = dist[v] + 1;
q.push(i);
}
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
cerr << dist[i] << ' ';
if (dist[i] <= 2 && dist[i] > 0) {
ans++;
}
}
cerr << '\n';
cout << ans << '\n';
}
signed main() {
#ifdef DEBUG
freopen("C.in", "r", stdin);
freopen("C.out", "w", stdout);
#else
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
while (cin >> m)
solve();
return 0;
}
Compilation message
relay.cpp: In function 'bool check(V, V)':
relay.cpp:280:20: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
idx += idx | idx + 1;
~~~~^~~
relay.cpp:294:8: warning: unused variable '_c' [-Wunused-variable]
bool _c = (A * C) > 0;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2052 ms |
2688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2052 ms |
2688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2052 ms |
2688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2052 ms |
2688 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
