글 읽기 - 시간초과가 자꾸 나네요 ㅠㅠ

jack2020 5년 전 0

일단 방법은 맞는 것 같습니다만...

nC3이다보니 워낙 시간이 많이 걸리는 것 같더군요 ㅠㅠ

뭐 좋은 다른 방법이 있을까요?

감사합니다 ㅠ

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<int> vec;
int cnt = 0;

struct dot {
	int x;
	int y;
} dot[1600];

struct vect {
	int x;
	int y;
} vec1, vec2, vec3;

int inner_product (vect v1, vect v2) {
	return v1.x * v2.x + v1.y * v2.y;
}

void check() {
	int a, b, c;
	a = vec[0]; b= vec[1]; c = vec[2];
	int ccw = (dot[a].x * dot[b].y + dot[b].x * dot[c].y + dot[c].x * dot[a].y)
		     -(dot[a].y * dot[b].x + dot[b].y * dot[c].x + dot[c].y * dot[a].x);
	if (ccw == 0) {
		return;
	}
	vec1.x = dot[a].x - dot[b].x;
	vec1.y = dot[a].y - dot[b].y;
	vec2.x = dot[b].x - dot[c].x;
	vec2.y = dot[b].y - dot[c].y;
	vec3.x = dot[c].x - dot[a].x;
	vec3.y = dot[c].y - dot[a].y;
	if (inner_product(vec1, vec2) == 0) {
		cnt++;
		return;
	}
	if (inner_product(vec2, vec3) == 0) {
		cnt++;
		return;
	}
	if (inner_product(vec3, vec1) == 0) {
		cnt++;
		return;
	}
	return;
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &dot[i].x, &dot[i].y);
	}
	string bitmask(3, 1);
	bitmask.resize(N, 0);
	do {
		vec.clear();
		for (int i = 0; i < N; i++) {
			if (bitmask[i]) {
				vec.push_back(i+1);
			}
		}
		check();
	} while (prev_permutation(bitmask.begin(), bitmask.end()));
	printf("%d", cnt);
	return 0;
}

messi 5년 전 0

풀어보지는 않아서 모르겠지만 저의 생각을 말해드리자면

점 1개를 고정하고, 그 점을 직각인 각으로 하는 삼각형의 개수를 구하면 될것 같네요.

각도 순으로 정렬한 후 스위핑을 하면 O(n^2 log n)입니다.

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

문제

문제

출처

ICPC

시간초과가 자꾸 나네요 ㅠㅠ

jack2020 5년 전 0

messi 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말