백준 BOJ 1945 - 직사각형

https://www.acmicpc.net/problem/1945

1945번: 직사각형

교내 백준랜덤디펜스 8번.

"원점을 지나는 직선" 이 힌트.

어떠한 점(x,y)과 (0,0) 사이 선을 그으면 그 선의 기울기는 y/x 임을 이용한다.

 

원점에서 그은 어떠한 직선이 직사각형을 지나려면

그 직선의 기울기가

직사각형의 왼쪽 위 꼭짓점에서 그은 선과

직사각형의 오른쪽 아래 꼭짓점에서 그은 선의 기울기 사이에 존재해야한다.

 

즉, 원점에서 그은 직선을 y=kx라고 하고,

입력되는 점의 좌표를 (a,b), (c,d) 라고 하면,

(b/c) <= k <= (d/a) 일 때 y=kx는 직사각형을 지나게 된다.

이 [(b/c), (d/a)]구간을 [s,e] 로 볼때,

주어지는 여러 [si, ei] 구간들에 대해서 구간이 최대한 많이 겹치는 경우를 찾으면 되고,

스위핑 알고리즘을 통해 O(NlogN) 으로 해결해줄 수 있다.

 

스위핑의 구현은

boj 1689 - 겹치는 선분 을 참고하면 좋을 듯 하다.

#include <bits/stdc++.h>
using namespace std;

set<double, greater<double>> point;
map<double,int> add;
map<double,int> sub;

int main(){
	int N,a,b,c,d;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> a >> b >> c >> d;
		point.insert((double)d/a);
		point.insert((double)b/c);
		add[(double)d/a]++;
		sub[(double)b/c]++;
	}
	
	int tmp = 0;
	int ans = -1;
	for(auto k : point){
		tmp += add[k];
		ans = max(ans, tmp);
		tmp -= sub[k];
	}
	cout << ans;
	return 0;
}