백준 25315 / C++

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

25315번: N수매화검법

 

[ 풀이 ] 

선분교차여부는 CCW로 잘 구해주면 된다. 이제 (m+1)*w[i] 이 부분을 처리해야 한다. 

서로 교차하는 것끼리 묶었다고 해보자.  묶은 것들은 m이 최대부터 시작하게 된다. (안벤 베기의 개수니까)

벤 후엔 계속 m은 감소하므로 따라서 묶은것들은 가중치가 작은것부터 처리해야 값이 최소가 된다. 

(그리디하게 최소는 최대와, 최대는 최소와 만나야 곱들의 합이 최소가 됨)

이제 구현해보자. 그냥 가중치가 작은순으로 정렬한 후 매번 교차점 개수를 세주면서 진행하면 된다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define x first
#define y second
pll s[2505], e[2505];
ll w[2505];

int ccw(pll a, pll b, pll c) {
	ll t = (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
	return (t > 0) - (t < 0);
}

int cross(pll a, pll b, pll c, pll d) {
	int abc = ccw(a, b, c);
	int abd = ccw(a, b, d);
	int cda = ccw(c, d, a);
	int cdb = ccw(c, d, b);
	if (abc * abd == 0 && cda * cdb == 0) {
		if (a > b) swap(a, b);
		if (c > d) swap(c, d);
		return (a <= d && c <= b);
	}
	return (abc * abd <= 0 && cda * cdb <= 0);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	vector<tuple<ll, ll, ll, ll, ll>>v;
	for (int i = 0; i < n; i++) {
		int sx, sy, ex, ey, w;
		cin >> sx >> sy >> ex >> ey >> w;
		v.push_back({ w, sx, sy, ex, ey });
	}
	sort(v.begin(), v.end()); 
	for (int i = 0; i < n; i++) {
		s[i] = { get<1>(v[i]), get<2>(v[i]) }; // 선분의 왼쪽끝점
		e[i] = { get<3>(v[i]), get<4>(v[i]) }; // 선분의 오른쪽끝점
		w[i] = get<0>(v[i]);
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		ll m = 0;
		for (int j = i + 1; j < n; j++) {
			if (cross(s[i], e[i], s[j], e[j])) m++; // 교차점 개수 count 
		}
		ans += (m + 1) * w[i];
	}
	cout << ans << '\n';
}