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

(追記) (追記ここまで)

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

1711번 - 직각삼각형

jack2020 7년 전 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 7년 전 0

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

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

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

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC