답안 #62445 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62445	2018-07-28T13:23:44 Z	Crown	Relay (COI16_relay)	C++14	100 / 100	115 ms	58948 KB

relay

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #62445

Compilation message

Subtask #1 18.0 / 18.0

Subtask #2 19.0 / 19.0

Subtask #3 20.0 / 20.0

Subtask #4 43.0 / 43.0

Subtask #1
18.0 / 18.0

Subtask #2
19.0 / 19.0

Subtask #3
20.0 / 20.0

Subtask #4
43.0 / 43.0