| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 233411 |
2020-05-20T12:45:57 Z |
TempoTemp |
Relay (COI16_relay) |
C++14 |
|
7 ms |
2688 KB |
// Pied!
#include<bits/stdc++.h>
#define x real()
#define y imag()
using namespace std;
typedef long double ld;
typedef complex < ld > point;
const int N = 300005;
int n, m, M[N], Mt[N], S[N];
point A[N], P[N];
pair < int , int > F[N];
mt19937 Rnd(time(0));
inline ld Cross(point a, point b)
{
return (a.x * b.y - a.y * b.x);
}
inline bool CCW(point a, point b, point c)
{
return (Cross(b - a, c - b) < 0);
}
inline bool OnRight(point p, int i)
{
i = (i + n) % n;
return (Cross(P[i + 1] - P[i], p - P[i]) <= 0);
}
inline bool Sees(point p, int i)
{
return (OnRight(p, i));
//return (OnRight(p, i) || OnRight(p, i - 1));
}
inline pair < int , int > GetIntv(point p)
{
int pv = abs((int)Rnd()) % n;
if (Cross(P[pv + 1] - P[pv], p - P[pv]) == 0)
return (GetIntv(p));
int le = pv + 1, ri = pv + n, md;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (CCW(p, P[pv], P[md]) == CCW(p, P[pv], P[pv + 1]))
le = md;
else
ri = md;
}
auto Gett = [](point p, int l, int r)
{
if (!Sees(p, l) && !Sees(p, r))
return make_pair(-1, -1);
bool w = Sees(p, l);
int le = l, ri = r, md;
if (w) ri ++;
while (ri - le > 1)
{
md = (le + ri) >> 1;
if (Sees(p, md) == w)
le = md;
else
ri = md;
}
if (w)
return make_pair(l, le);
return make_pair(ri, r);
};
if (ri == pv + n)
return (GetIntv(p));
pair < int , int > s1 = Gett(p, pv, le);
pair < int , int > s2 = Gett(p, ri, pv + n);
if (s1 == make_pair(-1, -1))
return (s2);
if (s2 == make_pair(-1, -1))
return (s1);
/*printf("%d ::: %d , %d\n", pv, le, ri);
printf("(%d %d) : (%d %d)\n", s1.first, s1.second, s2.first, s2.second);*/
if (s1.second + 1 == s2.first)
return make_pair(s1.first, s2.second);
assert(s1.first == pv && s2.second == pv + n);
s1 = make_pair(s2.first, s1.second + n);
if (s1.first >= n)
s1.first -= n, s1.second -= n;
return (s1);
}
int main()
{
scanf("%d", &m);
for (int i = 0; i < m; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
A[i] = point(a, b);
}
scanf("%d", &n);
for (int i = 0; i < n; i ++)
{
int a, b;
scanf("%d%d", &a, &b);
P[i] = P[i + n] = P[i + n + n] = point(a, b);
}
/*for (int i = 0; i < 2; i ++)
Rnd();
pair < int , int > X;
X = GetIntv(A[3 - 1]);
printf("%d , %d\n", X.first, X.second);
return 0;*/
for (int i = 0; i < m; i ++)
{
F[i] = GetIntv(A[i]);
if (F[i].first >= n)
F[i].first -= n, F[i].second -= n;
F[i].second ++;
//printf("%d :: %d , %d\n", i + 1, F[i].first, F[i].second);
}
M[0] = 1;
for (int w = 1; w <= 2; w ++)
{
memset(S, 0, sizeof(S));
memset(Mt, 0, sizeof(Mt));
for (int i = 0; i < m; i ++)
if (M[i])
{
S[F[i].first + 1] ++;
S[F[i].second + 1] --;
S[F[i].first + 1 + n] ++;
S[F[i].second + 1 + n] --;
}
for (int i = 1; i <= n + n + n; i ++)
S[i] += S[i - 1];
for (int i = 1; i <= n + n + n; i ++)
S[i] = S[i - 1] + (S[i] > 0);
for (int i = 0; i < m; i ++)
if (!M[i])
{
if (S[F[i].second] - S[F[i].first])
Mt[i] = 1;
if (S[F[i].second + n] - S[F[i].first + n])
Mt[i] = 1;
}
for (int i = 0; i < m; i ++)
if (Mt[i]) M[i] = 1;
}
/*for (int i = 0; i < m; i ++)
if (M[i]) printf("%d ", i + 1);
printf("\n");*/
int Cnt = 0;
for (int i = 1; i < m; i ++)
if (M[i]) Cnt ++;
return !printf("%d\n", Cnt);
}
Compilation message
relay.cpp: In function 'int main()':
relay.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
~~~~~^~~~~~~~~~
relay.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
relay.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
relay.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
