앳코더90 - 017 - Crossing Segments（★7）

https://atcoder.jp/contests/typical90/tasks/typical90_q

017 - Crossing Segments（★7）

 

원위에 N개의 점이 있고 M개의 선분이 있을 때, 각각의 선분을 이었을 때 교차점의 개수를 구하여라.

 

 

예제 1번의 예시를 그림으로 그리면 위와 같다.

 

먼저, 소문제 부터 풀어보자. 우리가 교차점이 생길려면은 다음과 같은 조건을 충족해야된다. 원에서 선분이 그려질 때 a,b를 잇는 직선과 c,d를 잇는 직선이 있다 할때, 하나의 점 c가 a,b 사이에 있고 다른 하나의 점 d가 a,b 외부에 있을 때 교차점이 생긴다. 이를 원이 아니라 펼쳐져 수직선위에 있다고 생각해도 무방하다. 이를 수식으로 바꿔서 코드로 표현하면 아래와 같다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>
#include <unordered_map>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const int INF = 2000000000;
const double pi = 3.14159265358979;
const int MOD = 100000;

void yesno(bool a)
{
	if (a)
		cout << "YES\n";
	else
		cout << "NO\n";
}

int N, M;
vector<pii> v;
int ans = 0;
int visited[300002];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	rep(i, M)
	{
		int a, b;
		cin >> a >> b;
		if (a > b)
			swap(a, b);
		v.push_back({ a,b });
	}

	sort(v.begin(), v.end());

	rep(i, M)
	{
		pii cur = v[i];
		for(int j = 0;j < i;j++)
		{
			pii dif = v[j];

			if ( 
				(cur.first < dif.first && dif.first < cur.second) &&
				(dif.second < cur.first   || cur.second < dif.second)
				)
			{
				ans++;
			}
			else if (
				(cur.first < dif.second && dif.second < cur.second) &&
				(dif.first < cur.first || cur.second < dif.first)
				)
			{
				ans++;
			}
		}
	}

	cout << ans;


	return 0;
}

 

선분의 시작점을 기준으로 정렬한 후 O(N^2)으로 각각 확인해준다. 하지만 이 같은 경우에는 나머지 과제를 해결 할 수 없다. 선분이 추가 될 때 마다 해당 선분이 특정 구간에 들어 갈 수 있는지 확인하는 방법을 세그먼트 트리를 이용해서 해결 하려 했으나.. 뭔가 잘 안됐다.

 

정해에서는 위 방법을 최적화 하기 어렵기에 여사건을 구하고 전체 경우의 수에서 빼는 방법으로 설명한다.