고급반 5주차 풀이 - 아자아자 (10 / 15)

+ 일부 문제에 대해 my3님의 기하 템플릿이 적용되었습니다. 미리 감사의 말씀을 드리고 시작하겠습니다.

 

1. [11758] CCW (Gold V)

문제에서 하라는대로 CCW를 구현해주면 됩니다.

int ccw(pl2 a, pl2 b, pl2 c){
	ll x = a.fr*b.sc + b.fr*c.sc + c.fr*a.sc;
	ll y = a.fr*c.sc + c.fr*b.sc + b.fr*a.sc;
	ll res = x-y;
	if (res > 0){ return 1; } if (res < 0){ return -1; } return 0;
}

void Main(){
	pl2 a, b, c; cin >> a.fr >> a.sc >> b.fr >> b.sc >> c.fr >> c.sc;
	cout << ccw(a, b, c);
}

2. [20150] 선분 교차 4 (Diamond V)

샤모스-호이 (Shamos-Hoey) 알고리즘의 구현 문제라고 한다.

축을 x + ky로 잡는 게 일반적인 것 같긴 하지만, 구현할 때는 (x, y) / (y, x) / (x+y, x-y)를 기준으로 3번 돌려줬다.

int n;
pl4 arr[200020], pnt[200020]; pl4 pos[400020];
multiset<Lin> lin;

bool smh(){
	sort(pos+1, pos+n+n+1);
	for (int i = 1; i <= n+n; i++){
		ll x = pos[i].fr.fr; bool ed = pos[i].fr.sc;
		ll y = pos[i].sc.fr; int idx = pos[i].sc.sc;
		//cout << "I " << i << endl << x << ' ' << y << " / " << ed << ' ' << idx << endl << flush;
		if (pnt[idx].fr.x == pnt[idx].sc.x){ continue; }
		Lin l(pnt[idx].fr, pnt[idx].sc);
		//cout << "L " << l.p1.x << ' ' << l.p1.y << " . " << l.p2.x << ' ' << l.p2.y << endl << flush;
		ptr = x;
		if (!ed){
			auto it = lin.insert(l);
			if (it != lin.begin()){ if (crs(*it, *prev(it))){ return 1; } }
			if (next(it) != lin.end()){ if (crs(*it, *next(it))){ return 1; } }
		}
		else{
			auto it = lin.lower_bound(l);
			//cout << (*it).p1.x << ' ' << (*it).p1.y << " / "
			// << (*it).p2.x << ' ' << (*it).p2.y << endl << flush;
			if (it != lin.begin() && next(it) != lin.end()){
				if (crs(*prev(it), *next(it))){ return 1; }
			}
			lin.erase(it);
		}
	}
	return 0;
}

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> arr[i].fr.x >> arr[i].fr.y >> arr[i].sc.x >> arr[i].sc.y;
		if (arr[i].fr > arr[i].sc){ swap(arr[i].fr, arr[i].sc); }
		assert(arr[i].fr != arr[i].sc);
	}
	for (int i = 1; i <= n; i++){
		pl2 p1 = { arr[i].fr.x, arr[i].fr.y };
		pl2 p2 = { arr[i].sc.x, arr[i].sc.y };
		if (p1 > p2){ swap(p1, p2); }
		pnt[i] = {p1, p2};
		pos[2*i-1] = { {p1.x, 0}, {p1.y, i} };
		pos[2*i] = { {p2.x, 1}, {p2.y, i} };
	} if (smh()){ cout << 1; return; } //cout << endl;
	for (int i = 1; i <= n; i++){
		pl2 p1 = { arr[i].fr.y, arr[i].fr.x };
		pl2 p2 = { arr[i].sc.y, arr[i].sc.x };
		if (p1 > p2){ swap(p1, p2); }
		pnt[i] = {p1, p2};
		pos[2*i-1] = { {p1.x, 0}, {p1.y, i} };
		pos[2*i] = { {p2.x, 1}, {p2.y, i} };
	} if (smh()){ cout << 1; return; } //cout << endl;
	for (int i = 1; i <= n; i++){
		pl2 p1 = { arr[i].fr.x+arr[i].fr.y, arr[i].fr.x-arr[i].fr.y };
		pl2 p2 = { arr[i].sc.x+arr[i].sc.y, arr[i].sc.x-arr[i].sc.y };
		if (p1 > p2){ swap(p1, p2); }
		pnt[i] = {p1, p2};
		pos[2*i-1] = { {p1.x, 0}, {p1.y, i} };
		pos[2*i] = { {p2.x, 1}, {p2.y, i} };
	} if (smh()){ cout << 1; return; } //cout << endl;
	cout << 0;
}

3. [20151] 선분 교차 5 (Diamond V)

Shamos-Hoey 응용 알고리즘입니다.

 

아래와 같은 처리를 해주면 됩니다.

• 정렬 순서에서 시작점 / 끝점 순서를 바꾸고
• 두 선분의 교차에서 끝점 교차를 제외하고
• 끝점에서 교차할 때 기울기 순서대로 Set에 잘 넣어주고 (Sweepline을 0.5씩 움직여주면 됩니다)
• 0.5를 처리하는 건 귀찮으니 좌표를 2배해주면 됩니다.

ll ptr;
class Lin{ public:
	pl2 p1, p2;
	Lin(){ p1 = {0, 0}; p2 = {0, 0}; }
	Lin(pl2 a, pl2 b){ p1 = a; p2 = b; }
};
inline ld f(const Lin& l, ll x){
	return (ld)(l.p2.y-l.p1.y) / (l.p2.x-l.p1.x) * (x-l.p1.x) + l.p1.y;
}
bool operator<(const Lin& l1, const Lin& l2){
	ld p1 = f(l1, ptr), p2 = f(l2, ptr);
	return p1 < p2;
}

int crs(const Lin& l1, const Lin& l2){
	//cout << "L1 " << l1.p1.x << ' ' << l1.p1.y << " . " << l1.p2.x << ' ' << l1.p2.y << endl << flush;
	//cout << "L2 " << l2.p1.x << ' ' << l2.p1.y << " . " << l2.p2.x << ' ' << l2.p2.y << endl << endl << flush;
	int c11 = ccw(l1.p1, l1.p2, l2.p1), c12 = ccw(l1.p1, l1.p2, l2.p2);
	int c21 = ccw(l2.p1, l2.p2, l1.p1), c22 = ccw(l2.p1, l2.p2, l1.p2);
	//cout << "CCW " << c11 << ' ' << c12 << ' ' << c21 << ' ' << c22 << endl << flush;
	if (c11 == 0 && c12 == 0){
		ll p11, p12, p21, p22;
		if (l1.p1.x == l1.p2.x){ p11 = l1.p1.y; p12 = l1.p2.y; p21 = l2.p1.y; p22 = l2.p2.y; }
		else{ p11 = l1.p1.x; p12 = l1.p2.x; p21 = l2.p1.x; p22 = l2.p2.x; }
		if (p11 > p21){ swap(p11, p21); swap(p12, p22); }
		//cout << p11 << ' ' << p12 << " | " << p21 << ' ' << p22 << endl << flush;
		return p12-p11 + p22-p21 > p22-p11;
	}
	//cout << (l1.p1 == l2.p1) << ' ' << (l1.p2 == l2.p2) << endl;
	if (l1.p1 == l2.p1 && l1.p2 == l2.p2){ return 1; }
	if (l1.p1 == l2.p1 && l1.p2 != l2.p2){ return -1; }
	if (l1.p1 != l2.p1 && l1.p2 == l2.p2){ return -2; }
	return c11 != c12 && c21 != c22;
}

int n;
pl4 arr[200020], pnt[200020]; pl4 pos[400020];
multiset<Lin> lin;

bool smh(){
	sort(pos+1, pos+n+n+1);
	for (int i = 1; i <= n+n; i++){
		ll x = pos[i].fr.fr; bool ed = pos[i].fr.sc;
		ll y = pos[i].sc.fr; int idx = pos[i].sc.sc;
		//cout << "I " << i << endl << x << ' ' << y << " / " << ed << ' ' << idx << endl << flush;
		if (pnt[idx].fr.x == pnt[idx].sc.x){ continue; }
		Lin l(pnt[idx].fr, pnt[idx].sc);
		//cout << "L " << l.p1.x << ' ' << l.p1.y << " . " << l.p2.x << ' ' << l.p2.y << endl << flush;
		ptr = x;
		if (!ed){
			bool flg = 0;
			auto it = lin.insert(l); rtr: ;
			//cout << (*it).p1.x << ' ' << (*it).p1.y << " / "
			// << (*it).p2.x << ' ' << (*it).p2.y << endl << flush;
			if (it != lin.begin()){
				int c = crs(*it, *prev(it));
				//cout << "C1 " << c << endl;
				if (c == 1){ return 1; }
				if (c == -1){
					lin.erase(it); ptr += 1; it = lin.insert(l); ptr -= 1;
					if (!flg){ flg = 1; goto rtr; }
				}
			}
			if (next(it) != lin.end()){
				int c = crs(*it, *next(it));
				//cout << "C2 " << c << endl;
				if (c == 1){ return 1; }
				if (c == -1){
					lin.erase(it); ptr += 1; it = lin.insert(l); ptr -= 1;
					if (!flg){ flg = 1; goto rtr; }
				}
			}
		}
		else{
			auto it = lin.lower_bound(l);
			if ((*it).p1 != l.p1 || (*it).p2 != l.p2){
				ptr -= 1; it = lin.lower_bound(l); ptr += 1;
			}
			//assert((*it).p1 == l.p1 && (*it).p2 == l.p2);
			//cout << (*it).p1.x << ' ' << (*it).p1.y << " / "
			// << (*it).p2.x << ' ' << (*it).p2.y << endl << flush;
			if (it != lin.begin() && next(it) != lin.end()){
				if (crs(*prev(it), *next(it)) == 1){ return 1; }
			}
			lin.erase(it);
		}
	}
	return 0;
}

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> arr[i].fr.x >> arr[i].fr.y >> arr[i].sc.x >> arr[i].sc.y;
		arr[i].fr.x *= 2; arr[i].fr.y *= 2;
		arr[i].sc.x *= 2; arr[i].sc.y *= 2;
		if (arr[i].fr > arr[i].sc){ swap(arr[i].fr, arr[i].sc); }
		assert(arr[i].fr != arr[i].sc);
	}
	for (int i = 1; i <= n; i++){
		pl2 p1 = { arr[i].fr.x, arr[i].fr.y };
		pl2 p2 = { arr[i].sc.x, arr[i].sc.y };
		if (p1 > p2){ swap(p1, p2); }
		pnt[i] = {p1, p2};
		pos[2*i-1] = { {p1.x, 0}, {p1.y, i} };
		pos[2*i] = { {p2.x, -1}, {p2.y, i} };
	} if (smh()){ cout << 1; return; } //cout << endl;
	for (int i = 1; i <= n; i++){
		pl2 p1 = { arr[i].fr.y, arr[i].fr.x };
		pl2 p2 = { arr[i].sc.y, arr[i].sc.x };
		if (p1 > p2){ swap(p1, p2); }
		pnt[i] = {p1, p2};
		pos[2*i-1] = { {p1.x, 0}, {p1.y, i} };
		pos[2*i] = { {p2.x, -1}, {p2.y, i} };
	} if (smh()){ cout << 1; return; } //cout << endl;
	for (int i = 1; i <= n; i++){
		pl2 p1 = { arr[i].fr.x+arr[i].fr.y, arr[i].fr.x-arr[i].fr.y };
		pl2 p2 = { arr[i].sc.x+arr[i].sc.y, arr[i].sc.x-arr[i].sc.y };
		if (p1 > p2){ swap(p1, p2); }
		pnt[i] = {p1, p2};
		pos[2*i-1] = { {p1.x, 0}, {p1.y, i} };
		pos[2*i] = { {p2.x, -1}, {p2.y, i} };
	} if (smh()){ cout << 1; return; } //cout << endl;
	cout << 0;
}

4. [2244] 민코프스키 합 (Platinum IV)

두 볼록다각형 \( A, B \)의 Minkowski Sum은 볼록다각형이다.

그러니, \( (Ax_{i}+Bx_{j}, Ay_{i}, By_{j}) \)의 모든 점을 구하고 Convex Hull을 돌려주면 된다.

int ccw(pl2 a, pl2 b, pl2 c){
	ll x = a.fr*b.sc + b.fr*c.sc + c.fr*a.sc;
	ll y = a.fr*c.sc + c.fr*b.sc + b.fr*a.sc;
	ll res = x-y;
	if (res > 0){ return 1; } if (res < 0){ return -1; } return 0;
}

pl2 arr[1020], brr[1020];
pl2 pos[1000020];

pl2 stk[1000020]; int sp;
inline void psh(pl2 p){ stk[sp] = p; sp += 1; }
inline void pop(){ sp -= 1; }

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	for (int i = 1; i <= m; i++){ cin >> brr[i].fr >> brr[i].sc; }
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			pos[(i-1)*m + j] = { arr[i].fr+brr[j].fr, arr[i].sc+brr[j].sc };
		}
	}
	int k = n*m;
	pl2 piv = {INF, INF}; int idx = 0;
	for (int i = 1; i <= n; i++){
		if (piv > pos[i]){ piv = pos[i]; idx = i; }
	}
	swap(pos[1], pos[idx]);
	sort(pos+2, pos+k+1, [piv](pl2 a, pl2 b){
		int res = ccw(piv, a, b);
		if (res > 0){ return true; } if (res < 0){ return false; }
		return a < b;
	});
	sp = 0; psh(pos[1]); psh(pos[2]);
	for (int i = 3; i <= k; i++){
		while (sp >= 2){
			int res = ccw(stk[sp-2], stk[sp-1], pos[i]);
			if (res != 1){ pop(); } else{ break; }
		}
		psh(pos[i]);
	}
	cout << sp << endl;
	for (int i = 0; i < sp; i++){ cout << stk[i].fr << ' ' << stk[i].sc << endl; }
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cout.setf(ios::fixed);
	cout.precision(PRECISION);
	Main();
}

5. [24458] Prison Break (Platinum III)

문제부터 접선처럼 생겼지만, 사실 접선 없이 풀 수 있다.

감옥을 이루는 선들을 모두 저장한 뒤, 감옥을 이루는 점과 간수들로 Convex Hull을 만들고

새로 만들어진 Convex Hull 중 '원래 감옥에 있던 선'들의 개수를 세주면 된다.

 

Convex Hull을 만들 때 CCW = 0인 경우도 포함해야 함에 주의하자.

set<pl4> edg;
pl2 arr[100020], brr[200020];

int sp = 0; pl2 stk[200020];
void psh(pl2 p){ stk[sp] = p; sp += 1; }
void pop(){ sp -= 1; }

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].x >> arr[i].y; brr[i] = arr[i]; }
	for (int i = 1; i <= n; i++){
		int i1 = i, i2 = i+1; if (i2 > n){ i2 -= n; }
		edg.insert({ arr[i1], arr[i2] }); edg.insert({ arr[i2], arr[i1] });
	}
	int m; cin >> m;
	for (int i = 1; i <= m; i++){ cin >> brr[n+i].x >> brr[n+i].y; }
	m += n;
	pl2 piv = {1e15, 1e15}; int idx = 0;
	for (int i = 1; i <= m; i++){
		if (piv > brr[i]){ piv = brr[i]; idx = i; }
	}
	swap(brr[1], brr[idx]);
	sort(brr+2, brr+m+1, [piv](pl2 a, pl2 b){
		int res = ccw(piv, a, b);
		if (res != 0){ return res > 0; } return dis(piv, a) < dis(piv, b);
	});
	sp = 0; psh(brr[1]); psh(brr[2]);
	for (int i = 3; i <= m; i++){
		while (sp >= 2){
			if (ccw(stk[sp-2], stk[sp-1], brr[i]) == -1){ pop(); }
			else{ break; }
		}
		psh(brr[i]);
	}
	for (int i = m-1; i > 1; i--){
		if (ccw(stk[0], brr[i], stk[sp-1]) == 0){ psh(brr[i]); }
		else{ break; }
	}
	int ans = 0;
	for (int i = 0; i < sp; i++){
		int i1 = i, i2 = i+1; if (i2 >= sp){ i2 -= sp; }
		if (edg.count({stk[i1], stk[i2]})){ ans += 1; }
	}
	cout << ans;
}

접선을 사용하지 않는 풀이를 알려주신 my3님 감사합니다.

6. [1310] 달리기 코스 (Platinum II)

Well-known 가장 먼 두 점 찾는 문제.

Convex Hull을 돌리고 Rotating Calipers를 박으면 풀린다.

int ccw(pl2 a, pl2 b, pl2 c){
	ll x = a.fr*b.sc + b.fr*c.sc + c.fr*a.sc;
	ll y = a.fr*c.sc + c.fr*b.sc + b.fr*a.sc;
	ll res = x-y;
	if (res > 0){ return 1; } if (res < 0){ return -1; } return 0;
}

int n, m;

pl2 pos[100020]; pl2 stk[100020]; int sp = 0;
inline void psh(pl2 p){ stk[sp] = p; sp += 1; }
inline void pop(){ sp -= 1; }

ll val = 0;
inline void upd(int i, int j){
	pl2 p1 = stk[i], p2 = stk[j];
	ll dy = p1.fr - p2.fr, dx = p1.sc - p2.sc;
	ll res = dy*dy + dx*dx;
	//cout << "UPD " << i << ' ' << j << " = " << p1.fr << ' ' << p1.sc << " / " << p2.fr << ' ' << p2.sc << " -> " << res << endl;
	val = max(val, res);
}

ll f(){ val = 0;
	pl2 piv = {INF, INF}; int idx = 0;
	for (int i = 1; i <= n; i++){
		if (piv > pos[i]){ piv = pos[i]; idx = i; }
	}
	swap(pos[1], pos[idx]);
	sort(pos+2, pos+n+1, [piv](pl2 a, pl2 b){
		int res = ccw(piv, a, b);
		if (res > 0){ return true; } if (res < 0){ return false; }
		return a < b;
	});
	sp = 0; psh(pos[1]); psh(pos[2]);
	for (int i = 3; i <= n; i++){
		while (sp >= 2){
			int res = ccw(stk[sp-2], stk[sp-1], pos[i]);
			if (res != 1){ pop(); } else{ break; }
		}
		psh(pos[i]);
	}
	//cout << "X " << x << ": ";
	//for (int i = 0; i < sp; i++){ cout << stk[i].fr << ' ' << stk[i].sc << "   "; }
	//cout << endl;
	int i = 0, j = 0;
	for (int i = 0; i < sp; i++){
		while (j < sp){
			int ip = (i+1) % sp, jp = (j+1) % sp;
			pl2 l = { stk[ip].fr - stk[i].fr, stk[ip].sc - stk[i].sc };
			pl2 r = { stk[jp].fr - stk[j].fr, stk[jp].sc - stk[j].sc };
			if (ccw({0, 0}, l, r) < 0){ break; }
			upd(i, j); j += 1;
		}
		if (j < sp){ upd(i, j); }
	}
	return val;
}

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){ cin >> pos[i].fr >> pos[i].sc; }
	ll ans = f();
	cout << val;
}

7. [4225] 쓰레기 슈트 (Platinum III)

쓰레기를 Convex Hull로 다시 만들어도 답은 변하지 않는다.

그런데 Convex하게 만들면 좋은 점이, 문제를 "가장 먼 점과 직선 사이의 거리"로 바꿔버릴 수 있다.

게다가, N도 작아서 직선과 점을 총 \( O(N^2) \)에 잡아줄 수 있다.

 

요약하자면, \( P_{i} \rightarrow P_{i+1} \)인 직선과 점 \( P_{j} \)의 거리를 다 재준 뒤, 가장 먼 값을 출력해주면 된다.

 

출력값이 소수점 이하 3자리에서 "올림"임에 주의하자.

pl2 arr[120];

int sp = 0; pl2 stk[200020];
void psh(pl2 p){ stk[sp] = p; sp += 1; }
void pop(){ sp -= 1; }

void Main(){
	for (int tt = 1; ; tt++){
		int n; cin >> n;
		if (n == 0){ return; }
		cout << "Case " << tt << ": ";
		for (int i = 1; i <= n; i++){ cin >> arr[i].x >> arr[i].y; }
		pl2 piv = {1e15, 1e15}; int idx = 0;
		for (int i = 1; i <= n; i++){
			if (piv > arr[i]){ piv = arr[i]; idx = i; }
		}
		swap(arr[1], arr[idx]);
		sort(arr+2, arr+n+1, [piv](pl2 a, pl2 b){
			int res = ccw(piv, a, b);
			if (res != 0){ return res > 0; } return dis(piv, a) < dis(piv, b);
		});
		sp = 0; psh(arr[1]); psh(arr[2]);
		for (int i = 3; i <= n; i++){
			while (sp >= 2){
				if (ccw(stk[sp-2], stk[sp-1], arr[i]) != 1){ pop(); }
				else{ break; }
			}
			psh(arr[i]);
		}
		ld ans = 9e18;
		for (int i = 0; i < sp; i++){
			int i1 = i, i2 = i+1; if (i2 >= sp){ i2 -= sp; }
			pl3 l;
			if (stk[i1].x == stk[i2].x){ l = { {1, 0}, -stk[i1].x }; }
			else{
				ll x1 = stk[i1].x, y1 = stk[i1].y;
				ll x2 = stk[i2].x, y2 = stk[i2].y;
				l = { { y2-y1, -(x2-x1) }, -(y2-y1)*x1 + y1*(x2-x1) };
			}
			ll a = l.fr.fr, b = l.fr.sc, c = l.sc;
			//cout << stk[i1].x << ' ' << stk[i1].y << "   "
			//	 << stk[i2].x << ' ' << stk[i2].y << "   "
			//	 << a << ' ' << b << ' ' << c << endl;
			ld res = 0;
			for (int j = 0; j < sp; j++){
				if (j==i1 || j==i2){ continue; }
				ll x = stk[j].fr, y = stk[j].sc;
				ll num = a*x + b*y + c; num *= num;
				ll den = a*a + b*b;
				ld val = (ld)num/den;
				res = max(res, val);
			}
			ans = min(ans, res);
		}
		cout << sqrt(ans)+0.005-eps << endl;
	}
}

8. [13310] 먼 별 (Diamond V)

어떤 임의의 두 별 \( a, b \)의 거리는 시간이 지날수록 가까워지다가 멀어지게 된다.

즉, 아래로 볼록한 함수의 형태를 띄게 된다.

그리고, 아래로 볼록한 함수들을 max해도 아래로 볼록한 함수가 나온다.

 

그러니, 삼분탐색을 통해 아래로 볼록한 함수에서의 답을 구할 수 있다.

 

시간 \( t \)가 정해지면 문제는 자명하게 "가장 먼 두 점의 거리"가 되니,

시간 \( t \)를 입력받은 뒤 이를 토대로 점을 찍고 Convex Hull을 만든 뒤 Rotating Calipers를 돌려주는 함수를 만들면 구현이 편해진다.

int ccw(pl2 a, pl2 b, pl2 c){
	ll x = a.fr*b.sc + b.fr*c.sc + c.fr*a.sc;
	ll y = a.fr*c.sc + c.fr*b.sc + b.fr*a.sc;
	ll res = x-y;
	if (res > 0){ return 1; } if (res < 0){ return -1; } return 0;
}

int n, m;
pl4 arr[30020];

pl2 pos[30020]; pl2 stk[30020]; int sp = 0;
inline void psh(pl2 p){ stk[sp] = p; sp += 1; }
inline void pop(){ sp -= 1; }

ll val = 0;
inline void upd(int i, int j){
	pl2 p1 = stk[i], p2 = stk[j];
	ll dy = p1.fr - p2.fr, dx = p1.sc - p2.sc;
	ll res = dy*dy + dx*dx;
	//cout << "UPD " << i << ' ' << j << " = " << p1.fr << ' ' << p1.sc << " / " << p2.fr << ' ' << p2.sc << " -> " << res << endl;
	val = max(val, res);
}

ll f(ll x){ val = 0;
	for (int i = 1; i <= n; i++){
		pos[i].fr = arr[i].fr.fr + arr[i].sc.fr*x;
		pos[i].sc = arr[i].fr.sc + arr[i].sc.sc*x;
	}
	pl2 piv = {INF, INF}; int idx = 0;
	for (int i = 1; i <= n; i++){
		if (piv > pos[i]){ piv = pos[i]; idx = i; }
	}
	swap(pos[1], pos[idx]);
	sort(pos+2, pos+n+1, [piv](pl2 a, pl2 b){
		int res = ccw(piv, a, b);
		if (res > 0){ return true; } if (res < 0){ return false; }
		return a < b;
	});
	sp = 0; psh(pos[1]); psh(pos[2]);
	for (int i = 3; i <= n; i++){
		while (sp >= 2){
			int res = ccw(stk[sp-2], stk[sp-1], pos[i]);
			if (res != 1){ pop(); } else{ break; }
		}
		psh(pos[i]);
	}
	//cout << "X " << x << ": ";
	//for (int i = 0; i < sp; i++){ cout << stk[i].fr << ' ' << stk[i].sc << "   "; }
	//cout << endl;
	int i = 0, j = 0;
	for (int i = 0; i < sp; i++){
		while (j < sp){
			int ip = (i+1) % sp, jp = (j+1) % sp;
			pl2 l = { stk[ip].fr - stk[i].fr, stk[ip].sc - stk[i].sc };
			pl2 r = { stk[jp].fr - stk[j].fr, stk[jp].sc - stk[j].sc };
			if (ccw({0, 0}, l, r) < 0){ break; }
			upd(i, j); j += 1;
		}
		if (j < sp){ upd(i, j); }
	}
	return val;
}

void Main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> arr[i].fr.fr >> arr[i].fr.sc >> arr[i].sc.fr >> arr[i].sc.sc;
	}
	ll st = 0, ed = m;
	while (st+1 < ed-1){
		ll m1 = (st+st+ed) / 3, m2 = (st+ed+ed) / 3;
		ll r1 = f(m1), r2 = f(m2);
		if (r1 > r2){ st = m1; } else{ ed = m2; }
	}
	pl2 ans = {f(st), st};
	for (int i = st; i <= ed; i++){
		pl2 res = {f(i), i};
		ans = min(ans, res);
	}
	cout << ans.sc << endl << ans.fr;
}

9. [20670] 미스테리 싸인 (Platinum III)

그냥 Point in Convex Polygon과 쿼리 문제.

 

\( A \) 밖에 있거나 \( B \) 안에 있는 점의 개수를 세주면 된다.

친절하게도, 점이 다각형의 외곽선에는 주어지지 않으니 Case Work같은 것도 없다.

그래도 제한은 크니까 \( O(\log N) \)만에 Point in Convex Polygon을 판별해주면 된다.

 

규칙을 어기는 점이 없다면 YES를 출력해야 함에 주의하자.

int n, m, k;
vector<pll> a, b;
vector<pllll> au, al, bu, bl;

inline void g(vector<pll>& v, vector<pllll>& u, vector<pllll>& l){
	int vl = v.size();
	for (int i = 1; i < vl; i++){
		//cout << i << ' ' << i-1 << endl;
		ll x1 = v[i-1].fr, x2 = v[i].fr;
		if (x1 < x2){ l.push_back({v[i-1], v[i]}); }
		if (x2 < x1){
			//cout << v[i].fr << ' ' << v[i].sc << endl;
			//cout << v[i-1].fr << ' ' << v[i-1].sc <<endl;
			u.push_back({v[i], v[i-1]});
		}
	}
	sort(all(u), [](pllll a, pllll b){
		return a.fr.fr < b.fr.fr;
	});
	sort(all(l), [](pllll a, pllll b){
		return a.fr.fr < b.fr.fr;
	});
	//for (pllll v : u){
	//	cout << v.fr.fr << ' ' << v.fr.sc << ' ' << v.sc.fr << ' ' << v.sc.sc << endl;
	//}
	//cout << endl << endl;
}

inline ld h(vector<pllll>& v, ll x){
	auto iu = lower_bound(all(v), x, [](pllll a, ll x){
		return a.sc.fr < x;
	});
	pllll p = *iu;
	//cout << p.fr.fr << ' ' << p.fr.sc << ' ' << p.sc.fr << ' ' << p.sc.sc << endl;
	ld yd = p.sc.sc - p.fr.sc, xd = p.sc.fr - p.fr.fr;
	return yd / xd * (x - p.fr.fr) + p.fr.sc;
}

inline bool f(vector<pllll>& u, vector<pllll>& l, pll p, int us){
	ll mnx = u[0].fr.fr, mxx = u[us-1].sc.fr;
	//cout << mnx << ' ' << p.fr << ' ' << mxx << endl;
	if (mnx >= p.fr || p.fr >= mxx){ return false; }
	ld uy = h(u, p.fr);
	ld ly = h(l, p.fr);
	//cout << p.fr << ' ' << p.sc << ' ' << ly << ' ' << p.sc << ' ' << uy << endl;
	return ly-err <= p.sc && p.sc <= uy+err;
}

void Main(){
	cin >> n >> m >> k;
	a.resize(n+1);
	b.resize(m+1);
	for (int i = 1; i <= n; i++){
		cin >> a[i].fr >> a[i].sc;
	}
	a[0] = a[n];
	g(a, au, al);
	int aus = au.size();
	for (int i = 1; i <= m; i++){
		cin >> b[i].fr >> b[i].sc;
	}
	b[0] = b[m];
	g(b, bu, bl);
	int bus = bu.size();
	int cnt = 0;
	while (k--){
		pll p;
		cin >> p.fr >> p.sc;
		bool ain = f(au, al, p, aus);
		//cout << endl;
		bool bin = f(bu, bl, p, bus);
		//cout << endl << endl;
		//cout << ain << ' ' << bin << endl << endl;
		if (!ain || bin){ cnt += 1; }
	}
	if (cnt == 0){ cout << "YES"; }
	else{ cout << cnt; }
}

10. [24895] 다트 (Diamond V)

문제에서 뭘 하라는 지 다 나와있습니다.

\( N \) 제한 때문에 사실상 모든 과정에서 이진 탐색으로 \( O(\log N) \) 때려야 하는게 어렵지만요.

const ll mod = 1e9 + 7;

int n; pl2 arr[50020];

inline int nxt(int idx){ return (idx+1) % n; }
inline int prv(int idx){ return (idx+n-1) % n; }

inline ll dar(pl2 p1, pl2 p2, pl2 p3){
	ll a = p1.x*p2.y + p2.x*p3.y + p3.x*p1.y;
	ll b = p1.x*p3.y + p3.x*p2.y + p2.x*p1.y;
	return abs(a-b);
}

int pin(pl2 p){
	int st = 1, ed = n-1;
	while (st+1 <= ed-1){
		int mid = st+ed >> 1;
		if (ccw(arr[0], arr[mid], p) < 0){ ed = mid; }
		else{ st = mid; }
	}
	ll a1 = dar(arr[0], arr[st], p), a2 = dar(arr[st], arr[ed], p);
	ll a3 = dar(arr[ed], arr[0], p), b = dar(arr[0], arr[st], arr[ed]);
	if (a1+a2+a3 == b){
		if (ccw(arr[st], arr[ed], p) == 0){ return 0; }
		if (st == 1 && ccw(arr[0], arr[st], p) == 0){ return 0; }
		if (ed == n-1 && ccw(arr[0], arr[ed], p) == 0){ return 0; }
		return 1;
	}
	return -1;
}

inline bool loc(pl2 p, pl2 p1, pl2 p2, pl2 p3, int dir){
	return dir*ccw(p, p1, p2) <= 0 && dir*ccw(p, p2, p3) >= 0;
}

int fix(pl2 p, int idx, int dir){
	if (dir > 0 && ccw(p, arr[idx], arr[prv(idx)]) == 0){ return prv(idx); }
	if (dir < 0 && ccw(p, arr[idx], arr[nxt(idx)]) == 0){ return nxt(idx); }
	return idx;
}

int tng(pl2 p, int dir){
	if (loc(p, arr[prv(0)], arr[0], arr[nxt(0)], dir)){ return fix(p, 0, dir); }
	int st = 0, ed = n;
	while (st+1 <= ed-1){
		int mid = st+ed >> 1;
		//cout << "TANGENT " << mid << endl;
		if (loc(p, arr[prv(mid)], arr[mid], arr[nxt(mid)], dir)){ return fix(p, mid, dir); }
		if (dir*ccw(p, arr[st], arr[nxt(st)]) < 0){
			if (dir*ccw(p, arr[mid], arr[nxt(mid)]) > 0){ ed = mid; }
			else if (dir*ccw(p, arr[mid], arr[st]) > 0){ st = mid; }
			else{ ed = mid; }
		}
		else{
			if (dir*ccw(p, arr[mid], arr[nxt(mid)]) < 0){ st = mid; }
			else if (dir*ccw(p, arr[mid], arr[st]) < 0){ st = mid; }
			else{ ed = mid; }
		}
	}
	//cout << "TANGENT " << st << ' ' << ed << endl;
	if (st != 0 && loc(p, arr[prv(st)], arr[st], arr[nxt(st)], dir)){ return fix(p, st, dir); }
	if (ed != n && loc(p, arr[prv(ed)], arr[ed], arr[nxt(ed)], dir)){ return fix(p, ed, dir); }
	return -1;
}

ll prf[50020];
inline ll qry(int st, int ed){
	if (st == ed){ return 0; }
	if (st > ed){ return prf[n-2] - qry(ed, st); }
	return prf[ed-1] - (st==0?0 : prf[st-1]) - dar(arr[0], arr[st], arr[ed]);
}

void Main(){
	int q; cin >> n >> q;
	for (int i = 0; i < n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	for (int i = 1; i < n-1; i++){ prf[i] = dar(arr[0], arr[i], arr[i+1]); }
	for (int i = 1; i < n-1; i++){ prf[i] += prf[i-1]; }
	ll res1 = 0, res2 = 0;
	int q1 = q; while (q1--){
		pl2 p; cin >> p.fr >> p.sc;
		int res = pin(p);
		if (res == 1){ res1 += qry(0, n-1); res1 %= mod; }
		if (res == -1){
			int i1 = tng(p, 1), i2 = tng(p, -1);
			//cout << "R-1 " << i1 << ' ' << i2 << ' ' << " = " << min(qry(i1, i2), qry(i2, i1)) << endl;
			res1 += min(qry(i1, i2), qry(i2, i1)); res1 %= mod;
		}
	}
	int q2 = q; while (q2--){
		pl2 p; cin >> p.fr >> p.sc;
		int res = pin(p);
		if (res == 1){ res2 += qry(0, n-1); res2 %= mod; }
		if (res == -1){
			int i1 = tng(p, 1), i2 = tng(p, -1);
			res2 += min(qry(i1, i2), qry(i2, i1)); res2 %= mod;
		}
	}
	if (res1 > res2){ cout << "ym"; } else if (res1 < res2){ cout << "hb"; } else{ cout << "same"; }
	cout << endl << res1 << ' ' << res2;
}

Not Solved

11. [7057] A highway and the seven dwarfs (Diamond V)

12. [10756] 편식 (Diamond IV)

13. [10785] Asteroids (Diamond I)

14. [18190] 촛불과 그림자 (Ruby V)

15. [4000] Kingdom Reunion (Ruby III)