글 읽기 - 반례 좀 부탁드려요!

joony94 4년 전 0

이 내용에서 틀린 부분이 어디일까요.. 테스트는 잘되는데 어떤 틀린 부분이 있나봅니다ㅠ

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

// 1004번
/***************************************************
해결방법: 출발점과 도착점이 몇 개의 원의
내부에 포함되어 있는지 세면 됌
한 점이 포함되어 있지 않은 원은 굳이 지날 필요가 없지만
포함되어 있는 점은 무조건 지나가야하니까
고등수학에 나오는 반지름과 원중심~좌표의 거리를 비교할건데
출발점이 한 원(C1)에 포함되어 있다면 도착점과 C1의 관계를 비교한다.
만약에 출발점과 도착점 둘 다 C1에 포함되어 있다면 지나는 원이 없기 때문이다.
즉 출발점과 C1과의 거리를 d1, 도착점과 C1과의 거리를 d2라 했을 때
d1<반지름<d2 || d2<반지름<d1의 관계에 있을 때만 통과
즉 (d1-R)*(d2-R)<0이면 그 원을 지난다는 의미가 될 것이다.
양번에 (d1+R)*(d2+R)을 곱해서 (d1^2-R^2)(d2^2-R^2)으로 하자. 양수니까 상관없음.
거리 구할 땐 제곱값이 편함.
****************************************************/

// 행성계 개수
int N;

// 출발점과 도착점
int x1, y1;
int x2, y2;

// 원 구조체 선언 및 포인터 배열 list 정의
typedef struct circle {
	int cx; // 원 중심 x좌표
	int cy; // 원 중심 y좌표
	int r; // 원 반지름
} circle;
circle *list;

void Init_() {
	scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
	scanf("%d", &N);
	list = (circle*)malloc(sizeof(circle)*N);
	int i;
	for (i = 0; i < N; i++) {
		scanf("%d %d %d", &list[i].cx, &list[i].cy, &list[i].r);
	}
}

int main() {
	
	int TC;
	int Tidx = 0;
	int answer;
	int idx = 0;
	int dis1, dis2; // dis1: 출발점~원중심의 제곱값, dis2:도착점~원중심의 제곱값
	int R; // R은 원의 반지름의 제곱값
	scanf("%d", &TC);
	while (Tidx < TC) {
		Init_();
		answer = 0;
		while (idx < N) {
			R = list[idx].r*list[idx].r;
			dis1 = (x1 - list[idx].cx)*(x1 - list[idx].cx) + (y1 - list[idx].cy)*(y1 - list[idx].cy);
			dis2 = (x2 - list[idx].cx)*(x2 - list[idx].cx) + (y2 - list[idx].cy)*(y2 - list[idx].cy);
			if ((dis1 - R)*(dis2 - R) < 0) answer++;
			idx++;
		}
		printf("%d\n", answer);
		Tidx++;
		free(list);
	}
	return 0;
}

1207koo 4년 전 1

x,y의 좌표의 범위를 보고

R, dis1, dis2의 범위를 생각해본다음

62번째 줄의 if문 내부의 식의 범위를 생각해봅시다.

1207koo 4년 전 0

반례)

1
-1000 -1000 1000 1000
1
0 0 1000

실제 답: 0/오답: 1

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

문제

문제

출처

ICPC

반례 좀 부탁드려요!

joony94 4년 전 0

1207koo 4년 전 1

1207koo 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말