글 읽기 - 2415번 문제 풀이법 토론하고 싶어요

appa 3년 전 0

문제의 해법이 다양한 거 같은데, 제 풀이보다 더 좋은 풀이가 있을거란 확신에 토론해보고 싶어서 글을 쓰게 되었습니다!

우선 문제를 풀어보지 않으셨다면 먼저 풀어보는 걸 추천드립니다.

전 일단 직사각형의 성질 2가지를 썼습니다.

1) 직사각형에서의 두 대각선의 길이는 서로 같다.

2) 직사각형에서의 두 대각선은 서로 다른 것을 이등분한다.(두 대각선의 중점이 같다.)

생성 가능한 모든 선분들을 만들어놓고, 길이 순으로(길이가 같다면 선분의 중점 x좌표 순으로) 정렬을 합니다.

그런 다음, 길이가 다르다면 더 이상 볼 필요없고, 선분의 중점 x좌표 또한 달라진다면 더 이상 볼 필요가 없기 때문에 대략 O(n^2 log n)의 시간복잡도를 가지는 것 같습니다.

여러분은 어떻게 푸셨나요?

											#include <cstdio>
#include <math.h>
#include <algorithm>
using namespace std;
#define MN 1505
typedef long long ll;
int n, m;
struct Point {
	int x, y;
	bool operator == (const Point p1) const {
		return (p1.x == x && p1.y == y);
	}
} p[MN], A, B, C;
struct Edge {
	Point a, b;
	ll length;
} e[MN*MN/2];
inline bool cmp(Edge e1, Edge e2) {
	if (e1.length == e2.length) return (e1.a.x+e1.b.x) < (e2.a.x+e2.b.x);
	return e1.length < e2.length;
}
inline double dist(Point p1, Point p2) {
	return (double)(sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(double)(p1.y-p2.y)*(p1.y-p2.y)+1e-5));
}
int main() {
	scanf("%d",&n);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d",&p[i].x,&p[i].y);
		for (int j = 1; j < i; j++) {
			e[++m].a = p[j]; e[m].b = p[i];
			e[m].length = (ll)(e[m].a.x-e[m].b.x)*(e[m].a.x-e[m].b.x)+(ll)(e[m].a.y-e[m].b.y)*(e[m].a.y-e[m].b.y);
		}
	}
	sort(e+1, e+m+1, cmp);
	int dx, dy, fx, fy;
	double res = 0;
	double area;
	for (int i = 1; i <= m; i++) {
		for (int j = i+1; j <= m; j++) {
			if (e[i].a == e[j].a || e[i].a == e[j].b || e[i].b == e[j].a || e[i].b == e[j].b) continue;
			if (e[i].length != e[j].length || e[i].a.x+e[i].b.x != e[j].a.x+e[j].b.x) break;
			if (e[i].a.y+e[i].b.y == e[j].a.y+e[j].b.y) {
				area =  dist(e[j].a, e[i].a)*dist(e[j].b, e[i].a)+(1e-5);
				if (res < area) res = area;
			}
		}
	}
	printf("%.0lf",res);
}
										

pl0892029 3년 전 2

O(N^4) 커팅이 더 빠른 신기한 문제네요. -_-;;

O(N^2 logN)으로 정렬한 후에 O(N^2)으로 정답을 구하는 방법이 가능합니다.

정렬할 때 직선의 기울기까지 고려하여 정렬하면 됩니다.

예전에 썼었던 글이 있으니 한번 보세요 ~_~

http://183.106.113.109/showArticle.php?messageid=1...

근데 현실은 (왜인지 모르겠지만) TLE를 수도없이 맞았습니다.

(그림 링크는 이전 더블릿 url이라서 깨져보입니다. ip 주소를 바꿔서 보시면 잘 보입니다.)

appa 3년 전 0

아하.. 사실 기울기도 고려해볼까 생각했었는데, 중복되는 점의 위치가 없다고 했으므로 2개로만 해도 후보군의 크기가 상수더라구요...

N^2개의 기울기를 계산하면서 생기는 연산의 시간이, 오히려 단순 비교연산을 상수배 더 하는 것보다 더 오래 걸린 것 같습니다.

그런데 그림이 깨져서 실수 연산을 하지 않는 법이 잘 보이지가 않네요ㅠㅠ...

답변 감사합니다!

hujub 3년 전 1

아직 풀어보지는 않아서 조심스럽지만..

벡터 내적을 이용해서 풀수 있지 않을까요

그러니깐, 우선 각 점들의 차이를 구합니다. 그리고 저장합니다. 여기서 O(N^2) 이 걸리겠네요.

다음, 방금 저장한 것들을 내적합니다. 그리고 0이 되는 것들만 추려내서 저장합니다. 여기서도 아마 O(N^2) 이 걸릴것 같네요.

그럼 이까지 세 점을 구하게 된겁니다. 내적시켰다는건 세점을 이용한거니깐..

다음, 그렇게 0이 된 것들 의 마지막 한 점을 찾아봅니다. 만약 존재한다면 max 로 정답을 업데이트 시켜줍니다.

음 제 생각대로만 된다면 O(N^2 + N^2 + ...) = O(N^2) 정도로 풀릴것 같은데..

음.. 이렇게 하면 구할 수 있지 않을까요? ㅋㅋ 시간나면 한번 풀어봐야겠어요.

appa 3년 전 1

오.. 벡터 내적은 생각안해봤는데 좋은 아이디어네요! 단지 그 벡터들을 이용해서 하나의 직사각형을 구성할 수 있느냐의 여부도 잘 체크해줘야겠군요!

pichulia 3년 전 2

모두를 대표해서 누구나 생각할 수 있는 가장 간단한 풀이를 써놓을게요..ㅋㅋㅋ

각 점에 대해서 구하는데, 선택된 점 하나를 중심으로 기울기를 다 구합니다.O(n)

그다음 얘를 각도를 기준으로 정렬해서O(nlogn)

더블포인터로 기울기가 90도가 되도록 i, j를 잡고. O(n)

이 두 점으로 만들어진 네번째 점이 존재하는지 체크합니다.O(1)

이리하면 n*(n+nlogn+n*1) = n^2logn인데...

대각선 길이가 같다는 성질 이용한건 진짜 특이한거같네요ㅋㅋㅋ굳굳

hujub 3년 전 0

ㅋㅋ백터내적으로 구할려고 했는데 O(n^2) 이 아니라 O(n^3) 이 되버려가지고ㅋㅋ 시간초과가 뜨네요

여러가지 아이디어들이 많으니깐 참 재밌는 문제네요

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

문제

문제

출처

ACM-ICPC

2415번 문제 풀이법 토론하고 싶어요

appa 3년 전 0

pl0892029 3년 전 2

appa 3년 전 0

hujub 3년 전 1

appa 3년 전 1

pichulia 3년 전 2

hujub 3년 전 0

Baekjoon Online Judge

채점 현황

문제

출처

ACM-ICPC

Coder's High

앱