글 읽기 - 1945번 증명 질문드립니다

smgod 4년 전 0

코드를 짜서 문제를 풀기는 했습니다만 이해가 잘 안됩니다.

acos 를 이용해 각을 왼쪽 위 오른쪽 아래 각을 계산해놓고 값을 저장해놓았습니다.

이제 이 범위 내에 가장 많이 포함되는 실수를 찾으면 되는 문제로 바뀌었다고 생각하고 풀려고 하니 경우의 수를 계산하기 너무 힘들어서 그냥 각 꼭지점을 지나는 acos값을 이용해 가장 많이 범위에 포함되는 값을 출력하니 맞았습니다를 받았습니다.

여기서 궁금한게 왜 항상 모든 답이 최소한 한개의 사각형의 꼭지점을 지나는지 증명을 하기 어려운것같습니다..

왜 답이 항상 이렇게되는지 알려주실 수 있나요 ?

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <math.h>
using namespace std;
struct vector2 {
	int x, y;
	double angle;
	explicit vector2(int x_=0, int y_=0):x(x_),y(y_)
	{}
	void makeangle()
	{
		angle = acos(double(x) / hypot(x, y));
	}
};
vector<pair<double, double>>vec_val;
int main(void)
{
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++)
	{
		int xbl, ybl, xtr, ytr;
		std::cin >> xbl >> ybl>> xtr>> ytr;
		vector2 veclh; // 레프트하이
		vector2 vecrl; // 라이트로우
		veclh.x = xbl;
		veclh.y = ytr;
		vecrl.x = xtr;
		vecrl.y = ybl;
		veclh.makeangle();
		vecrl.makeangle();
		vec_val.push_back(make_pair(veclh.angle, vecrl.angle));
	}
	int maxcnt = 0;
	for (int i = 0; i < vec_val.size(); i++)  // 첫번째가 left high  두번째가 right low
	{
		pair<double, double> pa = vec_val[i];
		int cnt = 0;
		int cnt2 = 0;
		for (int j = 0; j < vec_val.size(); j++)
		{
			if (pa.first <= vec_val[j].first && pa.first >= vec_val[j].second)
			{
				cnt++;
			}
			if (pa.second <= vec_val[j].first && pa.second >= vec_val[j].second)
			{
				cnt2++;
			}
		}
		if (maxcnt < cnt)
		{
			maxcnt = cnt;
		}
		if (maxcnt < cnt2)
		{
			maxcnt = cnt2;
		}
	}
	printf("%d", maxcnt);
	return 0;
}

lovinix 4년 전 0

증명이라고하긴 좀 그렇지만

엄밀히 말하면 답이 반드시 꼭지점을 지나야하는 것은 아니고 꼭지점을 지나도록 그릴 수 있는겁니다

질문자님의 풀이대로 얘기하자면 직사각형이 두 개 있고, 두 사각형이 원점과 이루는 각도가 각각 사각형1 (t1, t2), 사각형2 (t3, t4) (t1<t3<t2<t4)라 하면

답이 되는 각의 범위는 t2<=ans<=t3 로 항상 꼭지점이 양 끝이 되도록 줄어들기 때문입니다.

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

문제

문제

출처

ICPC

1945번 증명 질문드립니다

smgod 4년 전 0

lovinix 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말