LASER

AOJ LASER

더럽다 ㅋㅋ;;

SOL)
y = ax + b위에 있는 점들이 5개 이상이면 직선을 1개 count 해준다.
처음에 a를 더블형으로 저장했다가 오차 때문에 실패
기약분수 형태로 나타내어 분자 분모를 따로따로 키로써 사용하였다.
b도 마찬가지

y축에 평행한 직선일 경우는 따로 예외 처리를 해주었다.


[-] Collapse

#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
int gcd(int p, int q){
    if (q == 0) return p;
    return gcd(q, p % q);
}
int main(){
    int t; scanf("%d", &t);
    while (t--) {
        int n; scanf("%d", &n);
        vector<pair<int, int> > dot(n);
        for (int i = 0; i < n; i++)
            scanf("%d%d", &dot[i].first, &dot[i].second);

        map<pair<pair<int, int>, pair<int, int> >, int> info;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if (i == j) continue;
                int x1 = dot[i].first, y1 = dot[i].second;
                int x2 = dot[j].first, y2 = dot[j].second;
                if (x1 == x2)
                    info[make_pair(make_pair(30000+x1, 0), make_pair(0,0))]++;

                else{
                    int aGcd = gcd(abs(y1 - y2), abs(x1 - x2));
                    int y = (y1 - y2)/aGcd, x = (x1 - x2)/aGcd;
                    if (x < 0) y *= -1, x *= -1;

                    int bGcd = gcd(abs(y1 *x - y*x1), abs(x));
                    int bNmrt = (y1 *x - y*x1)/bGcd, bDenmrt = x/bGcd;
                    if (bDenmrt < 0) bNmrt *= -1, bDenmrt *= -1;

                    info[make_pair(make_pair(y, x), make_pair(bNmrt, bDenmrt))]++;
                }
            }
        }
        map<pair<pair<int, int>, pair<int, int> >, int>::iterator it = info.begin();
        int ans = 0;
        while (it != info.end()){
            if (it->second > 12) ans++;
            it++;
        }
        printf("%d\n", ans);
    }
}