[BOJ/백준][Gold1] 17611 : 직각다각형 (C++)

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

17611번: 직각다각형

 

 

[난이도] Gold1
[유형] 스위핑

[풀이]
가로 선분들과 세로 선분들을 나눠서 생각해보면
결국 가로 선분이 최대 몇개 겹칠 수 있는지, 세로 선분이 최대 몇개 겹칠 수 있는지를 각각 구해서
둘중 최댓값을 정답으로 출력하는 문제입니다.
번갈아 가면서 입력되는 가로 선분과 세로 선분을 각각 vector에 저장해줍니다.
a[i%2].push_back({l,1});
a[i%2].push_back({r,-1});
위와 같이 이런 스위핑 문제를 풀때 자주 사용하는 누적합 개념을 이용합니다.
선분이 시작되는 점에서 1을 더해주고 선분이 끝나는 점에서 1을 빼주면 어느 점에서 최대로 겹치는지
확인이 가능합니다.

 

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,ans;
pair<int,int> p[100000];
vector<pair<int,int>> a[2];
int main(){ 
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&p[i].first,&p[i].second);
    for(int i=1;i<=n;i++){
        int l,r,q=i,z=i-1;
        if(q==n) q=n-1,z=0;
        if(p[q].first==p[z].first) {
            l=min(p[q].second,p[z].second);
            r=max(p[q].second,p[z].second);
        }else{
            l=min(p[q].first,p[z].first);
            r=max(p[q].first,p[z].first);            
        }
        a[i%2].push_back({l,1});
        a[i%2].push_back({r,-1});
    }
    for(int i=0;i<2;i++){
        sort(a[i].begin(),a[i].end());
        int tmp=0;
        for(auto [t,v] : a[i]){
            tmp+=v;
            ans=max(tmp,ans);
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold1/17611.cpp