#7 - 20943번 카카오톡(오답)

문제

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

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

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

입력

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

N

a1 b1 c1

...

aN bN cN

출력

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

제한

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

나의 풀이

n개의 직선 중에 2개를 선택할 확률 - 기울기가 같은 직선을 2개 선택할 확률

 

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <iostream> #include <map> using namespace std;   int nC2(int n) {     return n * (n - 1) / 2; }   int main() {     int n;     cin >> n;       map<double, double> coe;       for (int i = 0;i < n;i++) {         double a, b, c;         cin >> a >> b >> c;           double m;         if (b != 0)             m = a / b;         else             m = NULL;           if (coe.find(m) == coe.end())             coe.insert(pair<double, double>(m, 1));         else             coe[m] += 1;     }       int result = nC2(n);       for (auto itr = coe.begin();itr != coe.end();itr++) {         if (itr->second > 1)             result -= nC2(itr->second);         else             continue;     }       cout << result;       return 0; } Colored by Color Scripter

cs