백준 20943 카카오톡

http://acmicpc.net/problem/20943 

20943번: 카카오톡

map을 사용해 푸는 문제였습니다.

교차하는 두 직선의 쌍을 구하는 문제였습니다. ax+by+c꼴로 주어지는데 결과적으로 기울기는 a/b가 됩니다.

두직선은 기울기가 같지않는 이상 교차하기때문에 각각 기울기로 분류하면됩니다. 실수계산을 피하기 위해서 a와 b의 최대공약수로 나눠준 a,b값을 pair로써 map의 key값으로 사용했고 각각 a=0 인경우 b=0인경우를 나눠서 구했습니다. 

#include<stdio.h>
#include<queue>
#include<vector>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int gcd(int x,int y){
    if(y==0){
        return x;
    }
    else{
        return gcd(y,x%y);
    }
}
map<pair<int,int>,int> m;
int main(){
    fast_io();
    int N;
    cin>>N;
    long long now=0;
    long long solve=0;
    long long now2=0;
    long long now3=0;
    for(int x=0;x<N;x++){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==0){
            now2++;
            continue;
        }
        if(b==0){
            now3++;
            continue;;
        }
        int k=gcd(abs(a),abs(b));
        long long ta=a/k;
        long long tb=b/k;
        if(ta*tb<0){
            m[{abs(ta),-abs(tb)}]++;
        }
        else m[{abs(ta),abs(tb)}]++;
    }
    long long k=N;
    N-=now2+now3;
    for(auto i : m){
        now+=i.second;
        solve+=(long long)((long long)N-now)*(long long)i.second;
    }
    solve+=(long long)(k-now2-now3)*now2;
    solve+=(long long)(k-now2-now3)*now3;
    solve+=now2*now3;
    cout<<solve;
}