글 읽기 - 이틀 째 틀린 부분을 찾아보고 있으나 반례를 찾지 못하여 질문합니다ㅜ

goodinet 5년 전 0

안녕하세요. 10255번 교차점 문제입니다.

코드는 길지만 메인 부분을 제외하고는 '알고리즘 문제 해결 전략 1'에서 제시된 코드를 그대로 옮겨온 코드입니다!

접근 방법은 다음과 같습니다.

직사각형의 네 점을 연결되어 있는 순서대로 a,b,c,d로, 선분의 양 끝 점을 x,y로 저장합니다.

(선분 ab, 선분 bc, 선분 cd, 선분 da)와 선분 xy이 만날 경우 ans에 +1이 추가됩니다.

이 때 점 a,b,c,d에서 선분 xy와 만날 경우 한 번 만남에도 불구하고 답이 2번 추가 될 수 있는데,

모든 a,b,c,d에 대하여 각 점이 선분 x,y위에 있을 경우 ans를 하나 빼주어 올바른 답을 출력하도록 합니다.

이 때 처리하지 않은 부분은 교점이 무한히 많은 경우로서 이는

매 테스트케이스마다 chk변수를 false로 초기화 해주는데

83번째 줄에서 볼 수 있듯이 평행한 두 선분이 만날 때, 양 끝에서 만나지 않으면

이 때는 교점이 무한히 많으므로 4를 출력하도록 합니다.

여러 풀이를 찾아보았고 접근 방법이 맞는 것 같으나 어느 부분에서 틀렸는 지 잘 모르겠습니다.

랜덤 데이터와 큰 수를 넣어봐도 틀린 예제를 찾지 못하였고

여러 입력에 대해 런타임에러를 발생해보아도 데이터 상에도 문제가 없어보이는데

대체 어떤 입력에 대해서 예외가 발생하는 지 모르겠습니다.

도움 주시면 감사하겠습니다!

#include <bits/stdc++.h>

using namespace std;

const double PI = 2.0 * acos(0.0);

bool chk = false;

struct vector2{
  double x,y;
  explicit vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_){}
  bool operator == (const vector2& rhs) const{
    return x == rhs.x && y == rhs.y;
  }
  bool operator < (const vector2& rhs) const{
    return x != rhs.x ? x < rhs.x : y < rhs.y;
  }
  //벡터의 덧셈과 뺄셈
  vector2 operator + (const vector2& rhs) const{
    return vector2(x + rhs.x, y + rhs.y);
  }
  vector2 operator - (const vector2& rhs) const{
    return vector2(x - rhs.x, y - rhs.y);
  }
  vector2 operator * (double rhs) const{
    return vector2(x * rhs, y * rhs);
  }
  //벡터의 길이 반환
  double norm() const{
    return hypot(x,y);
  }
  //단위벡터 (영벡터 제외)
  vector2 normalize() const{
    return vector2(x/norm(),y/norm());
  }
  //x축 양의 방향부터 이 벡터까지 반시계 방향으로 잰 각도
  double polar() const{
    return fmod(atan2(y,x) + 2*PI, 2*PI);
  }
  //내적 외적
  double dot(const vector2& rhs) const{
    return x * rhs.x + y * rhs.y;
  }
  double cross(const vector2& rhs) const{
    return x * rhs.y - rhs.x * y;
  }
  //사영한 결과
  vector2 project(const vector2& rhs) const{
    vector2 r = rhs.normalize();
    return r * r.dot(*this);
  }
};

//원점에서 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계방향이면 음수, 평행이면 0을 반환
double ccw(vector2 a, vector2 b){
  return a.cross(b);
}

//점 p를 기준으로 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계 방향이면 음수, 평행이면 0
double ccw(vector2 p, vector2 a, vector2 b){
  return ccw(a-p,b-p);
}

//(a,b)를 포함하는 선과 (c,d)를 포함하는 선의 교점을 x에 반환
//두 선이 평행이면 거짓, 아니면 참
const double EPSILON = 1e-9;
bool lineIntersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& x){
  double det = (b - a).cross(d - c);
  if(fabs(det) < EPSILON) return false;
  x = a + (b - a) * ((c - a).cross(d - c) / det);
  return true;
}

//(a,b) (c,d)가 평행한 두 선분일 때 이들이 겹치는 지 확인
//겹칠 경우 선분의 교점을 p에 반환
bool parallelSegments(vector2 a, vector2 b, vector2 c, vector2 d, vector2& p){
  if(b < a) swap(a,b);
  if(d < c) swap(c,d);
  //한 직선 위에 없거나 두 선분이 겹치지 않는 경우
  if(ccw(a,b,c)!=0 || b < c || d < a) return false;
  // 교차점 찾기
  if(a < c) p = c; else p = a;
  if(!(b == c || a == d)) chk = true;
  return true;
}
//a,b,p가 일직선에 있다고 가정 할 때, a,b를 잇는 선분위에 p가 있는 지
bool inBoundingRectangle(vector2 p, vector2 a, vector2 b){
  if(b < a) swap(a,b);
  return p==a || p==b || (a<p && p<b);
}
//(a,b)선분과 (c,d)선분의 교점을 p에 반환
//교점이 여러 개일 경우 아무 점 이나 반환
//두 선분이 교차하지 않을 경우 false를 반환
bool segmentIntersection(vector2 a, vector2 b, vector2 c, vector2 d, vector2& p){
  //두 직선이 평행인 경우
  if(!lineIntersection(a,b,c,d,p))
    return parallelSegments(a,b,c,d,p);
  //p가 두 선분에 포함되어 있는 경우에만 참
  return inBoundingRectangle(p,a,b) && inBoundingRectangle(p,c,d);
}

int main(){
  int T;
  scanf("%d",&T);
  while(T--){
    int sx,sy,ex,ey;
    scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
    int x1,y1,x2,y2;
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    vector2 a(sx,sy);
    vector2 b(ex,sy);
    vector2 c(ex,ey);
    vector2 d(sx,ey);
    vector2 x(x1,y1);
    vector2 y(x2,y2);
    vector2 p;
    chk = false;
    int ans = segmentIntersection(a,b,x,y,p) + segmentIntersection(b,c,x,y,p) + segmentIntersection(c,d,x,y,p) + segmentIntersection(d,a,x,y,p);
    if(ccw(a,x,y) == 0 && inBoundingRectangle(a,x,y)) ans--;
    if(ccw(b,x,y) == 0 && inBoundingRectangle(b,x,y)) ans--;
    if(ccw(c,x,y) == 0 && inBoundingRectangle(c,x,y)) ans--;
    if(ccw(d,x,y) == 0 && inBoundingRectangle(d,x,y)) ans--;
    if(chk) printf("4\n");
    else printf("%d\n",ans);
  }
}

rhs0266 5년 전 0

의심가는 부분은 ccw 함수가 double 형을 return하는데 0 이라는 자연수와 비교하는 부분입니다(line 119~122).

double형이기 때문에 생기는 오차 이슈를 확인해보시거나, 입력이 전부 정수로 이뤄지기 때문에 ccw함수를 int 형으로 변형해보세요.

goodinet 5년 전 0

ccw함수를 int형으로 바꾸고 몇몇 함수들을 이와 맞게 수정하니 맞았습니다! 감사합니다!

예외를 찾아보고 싶지만 힘들군요ㅠ

rhs0266 5년 전 2

double 형의 오차를 의도적으로 발생시키는 좋은 방법은 값을 크게 키우는 것입니다. 유효숫자가 많아질수록 오차 발생이 잦아집니다.

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

문제

문제

출처

ICPC

이틀 째 틀린 부분을 찾아보고 있으나 반례를 찾지 못하여 질문합니다ㅜ

goodinet 5년 전 0

rhs0266 5년 전 0

goodinet 5년 전 0

rhs0266 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말