Submission #62445

#	Time	Username	Problem	Language	Result	Execution time	Memory
62445		Crown	Relay (COI16_relay)	C++14	100 / 100	115 ms	58948 KiB

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 (stderr)

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 / 18
• Subtask 2: 19 / 19
• Subtask 3: 20 / 20
• Subtask 4: 43 / 43