[C++] 스위핑 알고리즘(Sweeping Algorithm)

스위핑 알고리즘(Sweeping Algorithm)

• 공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료 지점까지 지나가는데, 마주치는 요소들에 대해 판단이 되는 기준을 적용해 정답을 구하는 방식이다.
• 즉, 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 된다.

 

문제

 

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

2261번: 가장 가까운 두 점

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

const int INF = 1e9;

int dist(pair<int, int> p1, pair<int, int> p2) {
	return pow((p1.first - p2.first), 2) + pow((p1.second - p2.second), 2);
}

int main()
{
	int n;
	cin >> n;

	vector<pair<int, int>> p(n);
	for (int i = 0; i < n; i++)
		cin >> p[i].second >> p[i].first;

	sort(p.begin(), p.end(), [](pair<int, int> p1, pair<int, int> p2) {
		if (p1.second == p2.second)
			return p1.first < p2.first;
		return p1.second < p2.second;
		});

	set<pair<int, int>> s;
	s.insert(p[0]);
	s.insert(p[1]);

	int answer = dist(p[0], p[1]), start = 0;
	for (int i = 2; i < n; i++) {
		// y좌표가 answer 보다 큰 점 제외
		int x = p[i].second - p[start].second;
		while (start < i && x * x >= answer) {
			s.erase(p[start++]);
			x = p[i].second - p[start].second;
		}

		// x좌표가 (x좌표 ± answer) 거리 내에 있는 점 중 최단 거리를 answer로 갱신
		auto start = s.lower_bound({ p[i].first - sqrt(answer), -INF });
		auto end = s.upper_bound({ p[i].first + sqrt(answer), INF });
		for (auto j = start; j != end; j++)
			answer = min(answer, dist(p[i], *j));

		s.insert(p[i]);
	}
	cout << answer;
}

 

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

3392번: 화성 지도

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define SIZE 30002

struct Point {
    int x, y1, y2, val;
};

vector<Point> points;
int segtree[SIZE * 4];
int cnt[SIZE * 4];

void update(int node, int start, int end, int left, int right, int val)
{
    if (start > right || end < left)
        return;

    if (left <= start && end <= right) {
        cnt[node] += val;
    }
    else {
        int mid = (start + end) / 2;
        update(node * 2, start, mid, left, right, val);
        update(node * 2 + 1, mid + 1, end, left, right, val);
    }

    if (cnt[node])
        segtree[node] = end - start + 1;
    else {
        if (start == end)
            segtree[node] = 0;
        else
            segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}

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

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        Point temp;
        temp.y1 = y1 + 1, temp.y2 = y2 + 1;
        temp.x = x1, temp.val = 1;
        points.push_back(temp);
        temp.x = x2, temp.val = -1;
        points.push_back(temp);
    }

    sort(points.begin(), points.end(), [](Point& a, Point& b) {
        return a.x < b.x;
        });

    int answer = 0;
    for (int i = 0; i < points.size(); i++) {
        if (i > 0)
            answer += (points[i].x - points[i - 1].x) * segtree[1];
        update(1, 1, SIZE, points[i].y1, points[i].y2 - 1, points[i].val);
    }
    cout << answer;
}