[BOJ] 20943 카카오톡

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

20943번: 카카오톡

문제

카카오톡은 주식회사 카카오가 2010년 3월 18일 서비스를 시작한 글로벌 모바일 인스턴트 메신저로, 2020년 기준 4000$4\,000$만 명의 사용자가 등록돼 있고 시장 점유율이 96$96$%로 사실상 거의 모든 국민이 사용할 정도로 점유율이 매우 높다.

카카오의 지원하에 국렬이는 카카오톡의 특이한 오픈톡방에 대한 실험을 진행했다. 그에 대한 실험 내용은 다음과 같다. 실험에 대한 내용은 다음과 같다.

1.  N$N$명의 유저가 모인 특이한 오픈톡방이 있다.
2. 특이한 오픈톡방은 하나의 좌표 평면으로 구성되어 있으며, 각각 유저들은 좌표 평면 상의 서로 다른 직선 1$1$개를 할당받는다.
3. 각 유저들이 서로의 톡을 보기 위해서는 각 유저들의 직선이 서로 만나야 한다. 서로 만나지 않는다면 서로의 톡을 볼 수 없다.

이때, 국렬이는 특이한 오픈톡방 내에서 서로의 톡을 확인할 수 있는 유저의 쌍의 수를 구해야 한다. 국렬이는 너무 게을러서 이 실험을 대회에 떠넘겨버렸다. 당신은 상금을 위해 이 문제를 해결해야 한다.

 

입력

다음과 같이 입력이 주어진다.

 N

 a1 b1 c1 

...

 aN bN cN

출력

서로의 톡을 확인할 수 있는 유저의 쌍의 수를 출력하여라.

제한

•  N은 오픈 톡방에 모인 사람의 수를 의미하는 양의 정수다. (1≤N≤500000)
•  aix+biy+ci=0 a_i x + b_i y + c_i = 0은 i번째 유저가 할당받은 직선이다. (1≤i≤N)
•  −10^9≤ai,bi,ci≤10^9 (1≤i≤N)
•  (ai,bi)≠(0,0) (1≤i≤N)
• 다수의 유저들이 동일한 직선을 할당받는 경우는 존재하지 않는다.
• 입력으로 주어지는 모든 수는 정수다.

---

풀이

기울기가 같은 직선은 만나지 못한다는 것을 이용하여 풀면 된다.

a가 0일 경우는 예외처리를 해줘야 한다.

1. 기울기(b/a)를 key값으로 하여 map에 저장하고 value값을 +1 해준다.(a가 0일 경우 예외처리)
2. map 전체를 돌면서 전체 경우의 수에서 같은 직선이 포함된 경우를 빼주면 된다.

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

ll N;
map<double,ll> ma;

void input() {
    cin>>N;
    double a,b,c;
    for(int i=0;i<N;i++){
        cin>>a>>b>>c;
        if(a==0){
            ma[INF+1]++;
        }else{
            ma[b/a]++;
        }
    }
}

void init() {}


void solution() {
    //모든 직선이 만나는 경우의 수. 전체 직선의 개수에서 2개를 고르는 경우(NC2)
    ll ans=(N-1)*N/2;
    for (auto iter = ma.begin(); iter != ma.end(); ++iter) {
        ll n=iter->second;
        if(n!=1){
            //기울기가 같은 경우를 제외시킨다.
            ans-=(n-1)*n/2;
        }
    }
    cout<<ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}