oj.uz

Submission #62445

# Submission time Handle Problem Language Result Execution time Memory
62445 2018-07-28T13:23:44 Z Crown Relay (COI16_relay) C++14
100 / 100
 115 ms 58948 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)< 1e-6 || abs(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;
	int bad = 0;
	for(int i = 0; i< (int) ships.size(); i++)
	{
		bool fucked = true;
		if(ccw(p, L, ships[i])>= 0) reachL.pb(ships[i]), fucked = false;
		if(ccw(p, R, ships[i])<= 0) reachR.pb(ships[i]), fucked = false;
		if(intri(p, L, R, ships[i])) inTri.pb(ships[i]), fucked = false;
		if(fucked)
		{
			bad++;
			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;
		while(ccw(here, hull[detR], hull[inc(detR)])<= 0)
		{
			tR = here;
			detR = inc(detR);
		}
		if(ccw(before(detR), hull[detR], here)> 0 or ccw(hull[detR], after(detR), here)< 0) continue;
		double ori = find_cos(p, intersect(p, R, tR, hull[detR]), hull[detR]);
		double pos = find_cos(p, intersect(p, R, here, hull[detR]), hull[detR]);
		if(pos> ori) tR = here; 
	}
	for(int i = 0; i< (int) reachL.size(); i++)
	{
		point here = reachL[i];
		if(tL.x == 1e9+5) tL = here;
		while(ccw(here, hull[detL], hull[dec(detL)])>= 0)
		{
			tL = here;
			detL = dec(detL);
		}
		if(ccw(before(detL), hull[detL], here)< 0 or ccw(hull[detL], after(detL), here)> 0) continue;
		double ori = find_cos(p, intersect(p, L, tL, hull[detL]), hull[detL]);
		double pos = find_cos(p, intersect(p, L, here, hull[detL]), hull[detL]);
		if(pos> ori) tL = 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]);
			bad--;
		}
	}
	printf("%d\n", n-bad-1);
}

Compilation message

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);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 668 KB Output is correct
10 Correct 3 ms 808 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 668 KB Output is correct
10 Correct 3 ms 808 KB Output is correct
11 Correct 7 ms 1012 KB Output is correct
12 Correct 7 ms 1136 KB Output is correct
13 Correct 5 ms 1292 KB Output is correct
14 Correct 5 ms 1360 KB Output is correct
15 Correct 7 ms 1500 KB Output is correct
16 Correct 5 ms 1692 KB Output is correct
17 Correct 5 ms 1720 KB Output is correct
18 Correct 5 ms 1816 KB Output is correct
19 Correct 6 ms 1932 KB Output is correct
20 Correct 5 ms 2092 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 668 KB Output is correct
10 Correct 3 ms 808 KB Output is correct
11 Correct 55 ms 8888 KB Output is correct
12 Correct 48 ms 10872 KB Output is correct
13 Correct 50 ms 13004 KB Output is correct
14 Correct 72 ms 14748 KB Output is correct
15 Correct 55 ms 16876 KB Output is correct
16 Correct 57 ms 18844 KB Output is correct
17 Correct 56 ms 21288 KB Output is correct
18 Correct 61 ms 23276 KB Output is correct
19 Correct 65 ms 26052 KB Output is correct
20 Correct 62 ms 26804 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 3 ms 564 KB Output is correct
6 Correct 3 ms 564 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 668 KB Output is correct
10 Correct 3 ms 808 KB Output is correct
11 Correct 7 ms 1012 KB Output is correct
12 Correct 7 ms 1136 KB Output is correct
13 Correct 5 ms 1292 KB Output is correct
14 Correct 5 ms 1360 KB Output is correct
15 Correct 7 ms 1500 KB Output is correct
16 Correct 5 ms 1692 KB Output is correct
17 Correct 5 ms 1720 KB Output is correct
18 Correct 5 ms 1816 KB Output is correct
19 Correct 6 ms 1932 KB Output is correct
20 Correct 5 ms 2092 KB Output is correct
21 Correct 55 ms 8888 KB Output is correct
22 Correct 48 ms 10872 KB Output is correct
23 Correct 50 ms 13004 KB Output is correct
24 Correct 72 ms 14748 KB Output is correct
25 Correct 55 ms 16876 KB Output is correct
26 Correct 57 ms 18844 KB Output is correct
27 Correct 56 ms 21288 KB Output is correct
28 Correct 61 ms 23276 KB Output is correct
29 Correct 65 ms 26052 KB Output is correct
30 Correct 62 ms 26804 KB Output is correct
31 Correct 115 ms 32304 KB Output is correct
32 Correct 100 ms 36260 KB Output is correct
33 Correct 70 ms 37596 KB Output is correct
34 Correct 68 ms 40644 KB Output is correct
35 Correct 79 ms 44516 KB Output is correct
36 Correct 78 ms 47660 KB Output is correct
37 Correct 69 ms 49488 KB Output is correct
38 Correct 68 ms 52688 KB Output is correct
39 Correct 69 ms 56148 KB Output is correct
40 Correct 66 ms 58948 KB Output is correct