글 읽기 - 틀린 데가 어디일까요?

portableangel 6년 전 0

모든 점 i에 대해, i를 pivot으로 했을 때 다른 점들의 상대적인 기울기를 맵에 저장하고,

모든 기울기 m에 대해 이터레이팅하며 -1/m의 기울기를 갖는 점과 매칭시키는 경우의 수를 결과에 더했습니다.

기울기가 0인 점과 inf인 점을 매칭시키는 경우의 수는 따로 두 배하여 셌습니다.

이제 모든 삼각형이 두 번씩 세졌으므로, 마지막에 2로 나누어 출력했습니다.

사실 해당 로직을 1711번 동일한 문제에 예전에 구현한 코드는 정답이 뜨는데,

새로 구현한 아래의 코드는 롱앤서여서 어디가 틀린 것인지 궁금해서 질문드립니다.

#include <stdio.h>
#include <map>
#include <algorithm>

using namespace std;

typedef long long lli;

int gcd(int a, int b) {
    return b?gcd(b,a%b):a;
}

class frac {
public:
    int a, b;
    frac(int aa, int bb) {
        if(aa<0) {
            aa=-aa; bb=-bb;
        }
        int g=gcd(abs(aa),abs(bb));
        a=aa/g; b=bb/g;
    }
    bool operator<(const frac& k) const {
        return (lli)b*k.a<(lli)a*k.b;
    }
};

int x[1500], y[1500];
int n;

int main() {
	scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d %d",&x[i],&y[i]);
    int res=0;
    for(int i=0;i<n;i++) {
		map<frac,int> d;
        int h=0, v=0;
		for(int j=0;j<n;j++) if(i!=j) {
            int dx=x[i]-x[j], dy=y[i]-y[j];
            if(dx==0) h++;
            else if(dy==0) v++;
            else d[frac(dy,dx)]++;
        }
        for(map<frac,int>::iterator it=d.begin();it!=d.end();it++) {
        	int a=it->first.a, b=it->first.b;
            int cnt=d.count(frac(b,-a));
            if(cnt) res+=it->second*cnt;
        }
        res+=h*v*2;
    }
    printf("%d\n",res>>1);
    return 0;
}

sgchoi5 6년 전 1

원래 대회 TC 한 번 써 보심이... : )

http://gooddaytocode.blogspot....

portableangel 6년 전 0

제가 맛이 갔었네요. 죄송합니다. 47번 줄에 d.count(frac(b,-a))를 참조하면 0 또는 1이고, d[frac(b,-a)]를 참조해야 하네요..

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 데가 어디일까요?

portableangel 6년 전 0

sgchoi5 6년 전 1

portableangel 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말