| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 62429 |
2018-07-28T12:52:16 Z |
Crown |
Relay (COI16_relay) |
C++14 |
|
3 ms |
376 KB |
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
struct point
{
double x, y;
point(){}
point(double _x, double _y)
{
x = _x; y = _y;
}
point operator +(point rhs) const
{
return point(x+rhs.x, y+rhs.y);
}
point operator -(point rhs) const
{
return point(x-rhs.x, y-rhs.y);
}
};
int ccw(point a, point b, point c)
{
c = c-a; b = b-a;
double det = b.x*c.y - b.y*c.x;
if(abs(det)< 1e-4) return 0;
if(det> 0) return 1;
if(det< 0) return -1;
}
bool intri(point t1, point t2, point t3, point x)
{
int a = ccw(t1, t2, x);
int b = ccw(t2, t3, x);
int c = ccw(t3, t1, x);
int z = 0;
z += !a; z += !b; z += !c;
if(z>= 2) return true;
if(!a) return b == c;
if(!b) return a == c;
if(!c) return a == b;
return a == b && b == c;
}
int n, k;
vector<point> ships, hull;
point before(int ind)
{
if(ind) return hull[ind-1];
return hull.back();
}
point after(int ind)
{
if(ind+1 < (int) hull.size()) return hull[ind+1];
return hull[0];
}
int inc(int ind)
{
ind++;
if(ind == (int) hull.size()) ind = 0;
return ind;
}
int dec(int ind)
{
ind--;
if(ind == -1) ind = hull.size()-1;
return ind;
}
point intersect(point p1, point p2, point q1, point q2)
{
double a1 = p2.y-p1.y;
double b1 = p1.x-p2.x;
double c1 = p1.x*p2.y-p2.x*p1.y;
double a2 = q2.y-q1.y;
double b2 = q1.x-q2.x;
double c2 = q1.x*q2.y-q2.x*q1.y;
double x = (c1*b2-c2*b1)/(a1*b2-a2*b1);
double y = (c1*a2-c2*a1)/(b1*a2-b2*a1);
return point(x, y);
}
void print(point a)
{
printf("%lf %lf\n", a.x, a.y);
}
double find_cos(point a, point b, point c)
{
c = c-b; a = a-b;
double sz1 = sqrt(a.x*a.x+a.y*a.y);
double sz2 = sqrt(c.x*c.x+c.y*c.y);
if(abs(sz1*sz2)< 1e-6) return 0;
return (a.x*c.x+a.y*c.y)/(sz1*sz2);
}
int main()
{
scanf("%d", &n);
for(int i = 0; i< n; i++)
{
int x, y; scanf("%d %d", &x, &y);
ships.pb(point(1.0*x, 1.0*y));
}
scanf("%d", &k);
for(int i = 0; i< k; i++)
{
int x, y; scanf("%d %d", &x, &y);
hull.pb(point(1.0*x, 1.0*y));
}
point p = ships[0]; ships.erase(ships.begin());
point L, R;
int detL = 0, detR = 0;
for(int i = 0; i< (int) hull.size(); i++)
{
if(ccw(before(i), hull[i], p)>= 0 && ccw(hull[i], after(i), p)<= 0) detL = i, L = hull[i];
if(ccw(before(i), hull[i], p)<= 0 && ccw(hull[i], after(i), p)>= 0) detR = i, R = hull[i];
}
//print(L); print(R);
vector<point> unreach, reachL, reachR, inTri;
for(int i = 0; i< (int) ships.size(); i++)
{
if(ccw(p, L, ships[i])> 0) reachL.pb(ships[i]);
else if(ccw(p, R, ships[i])<= 0) reachR.pb(ships[i]);
else if(intri(p, L, R, ships[i])) inTri.pb(ships[i]);
else unreach.pb(ships[i]);
}
point tL(1e9+5, 1), tR(1e9+5, 1);
for(int i = 0; i< (int) reachR.size(); i++)
{
point here = reachR[i];
//printf("here"); print(here);
if(tR.x == 1e9+5) tR = here;
bool changed = false;
while(ccw(here, hull[detR], hull[inc(detR)])<= 0)
{
tR = here;
detR = inc(detR);
changed = true;
}
if(changed) continue;
double ori = find_cos(R, intersect(p, R, tR, hull[detR]), hull[detR]);
double pos = find_cos(R, intersect(p, R, here, hull[detR]), hull[detR]);
if(pos> ori) tR = here;
}
print(tR);
for(int i = 0; i< (int) reachL.size(); i++)
{
point here = reachL[i];
if(tL.x == 1e9+5) tL = here;
bool changed = false;
while(ccw(here, hull[detL], hull[dec(detL)])>= 0)
{
tL = here;
detL = dec(detL);
changed = true;
}
if(changed) continue;
double ori = find_cos(L, intersect(p, L, tL, hull[detL]), hull[detL]);
double pos = find_cos(L, intersect(p, L, here, hull[detL]), hull[detL]);
if(pos> ori) tR = here;
}
//print(hull[detR]);
//print(hull[detL]);
point cL = intersect(p, L, tL, hull[detL]), cR = intersect(p, R, tR, hull[detR]);
//printf("intersect\n");
//print(cL); print(cR);
vector<point> finally;
for(int i = 0; i< (int) unreach.size(); i++)
{
if((tR.x != 1e9+5 and (ccw(tR, hull[detR], unreach[i])<= 0 or intri(cR, hull[detR], R, unreach[i]))) or (tL.x != 1e9+5 and (ccw(tL, hull[detL], unreach[i])>= 0 or intri(cL, hull[detL], L, unreach[i]))))
{
finally.pb(unreach[i]);
}
}
printf("%d\n", (int) reachL.size()+reachR.size()+finally.size()+inTri.size());
}
Compilation message
relay.cpp: In function 'int main()':
relay.cpp:185:78: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<point>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d\n", (int) reachL.size()+reachR.size()+finally.size()+inTri.size());
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
relay.cpp: In function 'int ccw(point, point, point)':
relay.cpp:34:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
relay.cpp: In function 'int main()':
relay.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
relay.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
relay.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &k);
~~~~~^~~~~~~~~~
relay.cpp:117:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
