[정렬] 백준 2358 :: 평행선

평행선 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	1222	351	275	31.321%

문제

평면상에 n개의 점이 있다. 이 점들 중에 서로 다른 두 점을 선택하면 하나의 직선이 만들어진다. 이와 같이 직선을 만들었을 때, x축 또는 y축에 평행한 직선이 몇 개나 되는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 int 범위에서 주어진다. 만약 입력에 서로 같은 두 점이 주어지면, 그 두 점을 이용하여 직선을 만들 수 있다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1 

4
0 0
10 10
0 10
10 0

예제 출력 1 

4

 

 문제 풀이

1차 풀이 (  2648 KB,  40 ms )

문제가 굉장히 모호하다.

3

0 1   

0 2   

0 3   

인 경우에 답이 1이라고 한다.

x=0 위에 선이 몇개가 있든,  1개로 카운트 하라는 것 같다.

조합으로 생각하면,  "틀렸습니다"만 보게된다.

• 각각 x, y에 대해 정렬
• 2개 이상 같은 x를 가진 집합이 있다면,  정답에 +1
  
• 2개 이상 같은 y를 가진 집합이 있다면,  정답에 +1

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

using int32 = int32_t;
using int64 = int64_t;

struct point{
        int32 x = 0;
        int32 y = 0;
};
bool compareX(point &a, point &b) { return a.x < b.x; }
bool compareY(point &a, point &b) { return a.y < b.y; }

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

        int32 N, x, y;
        int64 ret = 0;
        bool distinct = false;
        cin >> N;
        point p[N];
        for(int32 i=0; i<N; i++){
                cin >> x >> y;
                p[i].x = x;
                p[i].y = y;
        }

        //! 세로선 검출.
        sort(p, p+N, compareX);
        distinct = true;
        for(int32 i=1; i<N; i++){
                if(p[i-1].x == p[i].x) {
                        if(distinct){
                                distinct = false;
                                ret++;
                        }
                }
                else {
                        distinct = true;
                }
        }

        //! 가로선 검출.
        sort(p, p+N, compareY);
        distinct = true;
        for(int32 i=1; i<N; i++){
                if(p[i-1].y == p[i].y) {
                        if(distinct){
                                distinct = false;
                                ret++;
                        }
                }
                else {
                        distinct = true;
                }
        }

        cout << ret;
}