글 읽기 - C++ ccw 안쓰고 푸는데 정신 나가겠습니다.. 제발 살려주세요,,,

hosun1804 2년 전 0

게시판에 있는 웬만한 반례는 다 통과하는것같고...

제가 짐작가는건 long long의 크기가 2^63 -1 까지 커버 가능하니까 denominator를 구해주는 과정의 연산이 최대 3*(2*10^6)^3일때 오버플로우나서 31%에서 계속 틀리는것이 아닌가인데..

진짜 정신 나가겠습니다 이문제때문에 역류성식도염이 제발하는것같은기분입니다

고수님들 제발 도와주세요..

#include <bits/stdc++.h>

using namespace std;

  double x[4];
  double y[4];
	double delta_x[2];
	double delta_y[2];
	double denominator, numerator;
	double  c1, c2;
	double  x_cross;

bool is_in(double target, double st, double ed){
	if(st > ed) swap(st,ed);
	return st <= target && target <= ed;
}

int main(){

  bool ans = false;
  for(int i =0  ; i< 4 ; ++i)
	cin >> x[i] >> y[i];
  if( ( (x[0] == x[2] ) && (y[0] == y[2]) )||
	  ( (x[0] == x[3] ) && (y[0] == y[3]) ) ||
	  ( (x[1] == x[2] ) && (y[1] == y[2]) ) ||
	  ( (x[1] == x[3] ) && (y[1] == y[3]) ) ){
	cout << 1;
	return 0;
  }
  delta_x[0] = x[1] - x[0];
  delta_x[1] = x[3] - x[2];
  delta_y[0] = y[1] - y[0];
  delta_y[1] = y[3] - y[2];
  
  denominator = (y[2] - y[0]) * delta_x[0] * delta_x[1] 
	+ x[0] * delta_x[1] * delta_y[0] - x[2] * delta_x[0] * delta_y[1];
  numerator = delta_x[1] * delta_y[0] - delta_x[0] * delta_y[1];
  if(numerator == 0){ // keisan hukanou
	if(delta_x[1] == 0 && delta_x[0] == 0){ // two lines are vertical
		ans = (x[0] == x[2]) && 
		( is_in(y[0],y[2],y[3]) 
		|| is_in(y[1],y[2],y[3])
		|| is_in(y[2],y[0],y[1]) 
		|| is_in(y[3],y[0],y[1]) );
	}
	// one vertical, one horizontal or parrallel
	else if(delta_x[0] == 0 && delta_y[1] == 0){
		ans = is_in(x[0], x[2], x[3]) && is_in(y[2], y[0], y[1]);
	}
	else if(delta_x[1] == 0 && delta_y[0] == 0){
		ans = is_in(y[0], y[2], y[3]) && is_in(x[2], x[0], x[1]);
	} 
	// both horizontal
	else if(delta_y[0] == 0 && delta_y[1] == 0){
		ans = (y[0] == y[2]) && 
		( is_in(x[0],x[2],x[3]) 
		|| is_in(x[1],x[2],x[3])
		|| is_in(x[2],x[0],x[1]) 
		|| is_in(x[3],x[0],x[1]) );
	}
	else{ 
		c1 = ( y[0] * delta_x[0] - x[0] * delta_y[0] ) * delta_x[1] ;
    c2 = ( y[2] * delta_x[1] - x[2] * delta_y[1] ) * delta_x[0] ;
		ans = (c1 == c2) && ( 
			is_in(x[0],x[2],x[3]) 
	    || is_in(x[1],x[2],x[3])
		  || is_in(x[2],x[0],x[1]) 
			|| is_in(x[3],x[0],x[1]) );
	}
	}
  else{
  x_cross = denominator / numerator ;
  //printf("%lfd/%lfd -> x_cross : %lf",denominator,numerator,x_cross);
	ans = ( 
		is_in(x_cross, x[0], x[1]) &&
		is_in(x_cross, x[2], x[3]) );
  }
  cout << ans;
  return 0;
}

bamgoesn 2년 전 2

반례입니다

1 2 1 1
1 0 2 1

정답: 0
출력: 1

2 0 1 0
1 2 1 1

정답: 0
출력: 1

2 0 2 1
2 2 0 1

정답: 0
출력: 1

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

문제

문제

출처

ICPC

C++ ccw 안쓰고 푸는데 정신 나가겠습니다.. 제발 살려주세요,,,

hosun1804 2년 전 0

bamgoesn 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말