Boj 2650) 교차점 개수

문제

백준 2650

설명

2차원 공간을 1차원 으로 매핑하면 문제가 간단해짐.

• 어차피 직사각형 위에서 움직이므로 가능함
• 교차하는건 두 선을 이루는 점이 번갈아가면서 오는 경우가 됨.

시간복잡도

O(\(N^2\))

코드

struct P { int p1, p2; };
P pt[51]; int ans[51];

inline int Intep(int t, int p) {
	switch (t)
	{
	case 1: return 1 * 1000 + p;
	case 4: return 2 * 1000 + p;
	case 2: return 3 * 1000 - p;
	case 3: return 4 * 1000 - p;
	}
}

inline bool Check(P& a, P& b)
{
	if (a.p1 < b.p1) 
		return b.p1 < a.p2 && a.p2 < b.p2; //  a1 b1 a2 b2
	else return a.p1 < b.p2 && b.p2 < a.p2; //  b1 a1 b2 a2
}

int main()
{
	fastio;
	int n;
	cin >> n;
	n /= 2;

	for (int i = 0; i < n; i++)
	{
		int t, p, p1, p2;
		
		cin >> t >> p;
		p1 = Intep(t, p);

		cin >> t >> p;
		p2 = Intep(t, p);

		pt[i].p1 = min(p1, p2);
		pt[i].p2 = max(p1, p2);
	}

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
		{
			bool cur = Check(pt[i], pt[j]);
			ans[i] += cur;
			ans[j] += cur;
		}

	cout << accumulate(ans, ans + n, 0) / 2 << endl;;
	cout << *max_element(ans, ans + n) << endl;;
}