| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 230849 |
2020-05-11T22:33:23 Z |
frodakcin |
Relay (COI16_relay) |
C++11 |
|
15 ms |
13056 KB |
#include <cstdio>
#include <cassert>
using ll = long long;
struct vec
{
public:
ll x, y;
vec(ll x=0, ll y=0) : x(x), y(y) {}
void in(){scanf("%lld%lld", &x, &y);}
ll operator / (vec o) const {return x*o.y-o.x*y;}
ll operator * (vec o) const {return x*o.x+y*o.y;}
vec& operator += (vec o) {return x+=o.x, y+=o.y, *this;}
vec& operator -= (vec o) {return x-=o.x, y-=o.y, *this;}
friend vec operator + (vec a, vec b) {return a += b;}
friend vec operator - (vec a, vec b) {return a -= b;}
};
const int MN = 2e5 + 10;
int N, M, low[MN], high[MN], ans;
bool mayday[MN];
vec a[MN], b[MN];
struct ray
{
public:
vec s, d;
};
ray bot, top;
int main(void)
{
assert(0);
scanf("%d", &N);
for(int i=0;i<N;++i)
a[i].in();
scanf("%d", &M);
for(int i=0;i<M;++i)
b[i].in(), b[i+M]=b[i];//for convenience
for(int i=0,l,r,m,u,v,z;i<N;++i)
{
vec x=a[i];
//printf("INFO FOR (id: %d), (%lld, %lld) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n", i+1, x.x, x.y);
z=0;
vec d=b[z]-x;
if(d/(b[1]-b[0]) == 0)
d=b[++z]-x;
if(d/(b[z+1]-b[z]) > 0)
{
l=0,r=M;
for(;r-l>1;)
{
m=l+(r-l)/2;
if(d/(b[m]-b[z]) < 0)
r=m;
else
l=m;
}
u=l;
}
else
u=z;
assert((b[u]-x)/(b[u+1]-x) <= 0);
//b[u] is on the same side as a[i]
d=b[u]-x;
l=u,r=u+M;
for(;r-l>1;)
{
m=l+(r-l)/2;
if(d/(b[m]-b[u]) < 0)
l=m;
else
r=m;
}
v=l;
//printf("VALS: %d %d\n", u, v);
assert((b[v]-x)/(b[v+1]-x) >= 0);
//u<->v cut the convex hull
//u is on closer side
//lower hull: v...u
{
l=v,r=u;
if(r<l)r+=M;
--l;
for(;r-l>1;)
{
m=l+(r-l)/2;
if((b[m]-x)/(b[m+1]-b[m])>0)
l=m;
else
r=m;
}
low[i] = r%M;
}
//upper hull: u...v
{
l=u,r=v;
if(r<l) r+=M;
--l;
for(;r-l>1;)
{
m=l+(r-l)/2;
if((b[m]-x)/(b[m+1]-b[m])<=0)
l=m;
else
r=m;
}
high[i] = r%M;
}
//printf("\tLOW: (%lld, %lld)\n", b[low[i]].x, b[low[i]].y);
//printf("\tHIGH: (%lld, %lld)\n", b[high[i]].x, b[high[i]].y);
//printf("\n");
assert((b[low[i]]-x)/(b[low[i]+1]-b[low[i]]) <= 0);
assert((b[low[i]+M-1]-x)/(b[low[i]]-b[low[i]+M-1]) > 0);
assert((b[high[i]]-x)/(b[high[i]+1]-b[high[i]]) > 0);
assert((b[high[i]+M-1]-x)/(b[high[i]]-b[high[i]+M-1]) <= 0);
}
bot = {b[low[0]], b[low[0]]-a[0]};
top = {b[high[0]], b[high[0]]-a[0]};
vec bot0 = b[low[0]]-a[0];
vec top0 = b[high[0]]-a[0];
for(int i=1;i<N;++i)
{
if(bot.d/(a[i]-bot.s)>=0 || top.d/(a[i]-top.s)<=0)
mayday[i] = 1;
else if((a[i]-top.s)/(a[i]-bot.s) >= 0)
mayday[i] = 1;
}
for(int i=1;i<N;++i)
if(mayday[i])
{
//printf("MAYDAY: (id: %d), (%lld, %lld)\n", i+1, a[i].x, a[i].y);
ray bot2 = {b[low[i]], b[low[i]]-a[i]};
ray top2 = {b[high[i]], b[high[i]]-a[i]};
if(bot0/bot2.d <= 0 && bot.d/bot2.d < 0)
bot = bot2;
if(top0/top2.d >= 0 && top.d/top2.d > 0)
top = top2;
}
if((top.s-a[0])/(bot.s-a[0]) <= 0)
return printf("%d\n", N-1), 0;
for(int i=1;i<N;++i)
{
bool relay=0;
if(bot.d/(a[i]-bot.s)>=0 || top.d/(a[i]-top.s)<=0)
relay = 1;
else if((a[i]-top.s)/(a[i]-bot.s) >= 0)
relay = 1;
if(relay)
{
++ans;
//printf("RELAY: (id: %d), (%lld, %lld)\n", i+1, a[i].x, a[i].y);
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
relay.cpp: In function 'int main()':
relay.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
relay.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &M);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
13056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
13056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
13056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
15 ms |
13056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
