2개의 댓글이 있습니다.
-
-
Apple_Cplus -
계산식 잘못된게 아닐까여? calc 바꾸니 맞네여
return x1-(double)y1*(x2-x1)/(y2-y1);
11년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
계산식 잘못된게 아닐까여? calc 바꾸니 맞네여
return x1-(double)y1*(x2-x1)/(y2-y1);
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
xesmaster
알고리즘이 맞는거 같은데 live archive에서 계속 WA를 뱉어내서
힘드네요..ㅠㅠ
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2254
일단 알고리즘은 모든 페어마다 엑스자로 y=0과 만나는 구간을 생성해서 이러한 페어마다의 구간(n^2개)의 교집합이 있는지 없는지를 체크하는 알고리즘인데요..
맞는 알고리즘인거같은데 계속 틀리네요. 기본적으로 n^2으로 걍 돌리면 TLE가 나오길래 도중에 커팅 코드를 집어넣엇는데 아무래도 double 타입 오차범위때문에 이러는거같은데 고칠수가 없네요 ㅠㅠ 유리수로 해봤는데 생각해보니x절편 구할때 분모에 10^14정도까지 올라가서 비교함수에서 곱셈 연산에서 overflow가 나서 long long타입으로 유리수를 줘도 안되고.. gcd로 분모분자 낮추는 코드를 집어넣으면 TLE가 나고.. 그렇다고 bignum으로 하자니 또 TLE 날꺼같고 ㅠㅠ 도와주세요..
11년 전