백준 2358 평행선

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

2358번: 평행선

문제 해설

평면 상의 n개의 점들 중 2개를 선택하여 x축 또는 y축에 평행한 직선이 몇 개나 되는지 알아내는 문제다.

만약 3개 이상의 점들이 한 직선을 이룬다면 직선의 수는 한 번만 센다.(중복 X)

동일한 점이 주어지는 경우 직선을 만들 수 있다고 한다.

>> 이 경우 무한개의 방향으로 뻗어나가는 직선 중 x축과 y축에 평행한 직선 2개를 센다.

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <vector>
#include <algorithm>
#include <set>
int main(){
    fio;
    int N; cin >> N;
    vector<pair<int, int> > by_x;   //(x, y);
    vector<pair<int, int> > by_y;   //(y, x);
    for(int i=0; i < N; i++){
        int x, y; cin >> x >> y;
        by_x.push_back(make_pair(x, y));
        by_y.push_back(make_pair(y, x));
    }
    
    //
    sort(by_x.begin(), by_x.end());
    sort(by_y.begin(), by_y.end());
    set<int> x_axis, y_axis;
    for(int i=0; i < by_x.size()-1; i++){
        if(by_x[i].first == by_x[i+1].first){
            x_axis.insert(by_x[i].first);
        }
    }
    for(int i=0; i < by_y.size()-1; i++){
        if(by_y[i].first == by_y[i+1].first){
            y_axis.insert(by_y[i].first);
        }
    }
    cout << x_axis.size() + y_axis.size();
    return 0;
}

코드 해설

n개의 점을 (x, y), (y, x)구조의 벡터에 저장한다.

각각의 벡터에서 이웃한 데이터의 첫번째 값이 같은 경우 x축 또는 y축에 평행한 직선을 만들 수 있다.

평행한 직선을 모두 set에 집어넣어 중복없이 저장한다.