ABC224 C - Triangle? C++ 해답 예
9540 단어 C++시합 프로그램 설계AtCoder경업자tech
문제.
사이트 축소판 그림에서 문제문을 인용하다.
문제문
xy 평면에는 1부터 N까지의 N개의 점이 있습니다.
점 i는 좌표(X i, Y i)에 위치하고 서로 다른 2점은 서로 다른 2점에 존재한다.
이 N점 중에서 3점을 선택할 때 선택한 3점을 선분으로 연결하는 그래픽을 양의 면적의 삼각형이 되는 점으로 선택하는 방법의 총 수를 계산합니다.
구속
i\neqj의 경우(X i, Y i)\neq(X j, Y j)
해답 예시
선택한 3점은 삼각형이 아닌 조건입니다.
N점 중 3개를 선택할 때 3점을 세그먼트로 연결하는 도면에는 양의 면적이 없습니다.는 3개의 점이 직선으로 정렬되는 조건이 있습니다.
또 N의 경우 최대 300으로 제한이 느슨해 N 중 3개 점을 선택할 때의 수를 모두 검색해 3개 점이 한 직선으로 배열됐는지 각각 판정하면 문제를 해결할 수 있다.
3점이 한 직선에 배열되어 있는지 판단하려면 3점 중 2점이 형성한 직선에 남은 1점이 있는지 판정하는 것이 좋다.
N에서 선택한 3점은 각각 (X i, Y i), (X j, Y j), (X k, Y k)(i
y - Y_i =\frac{Y_j - Y_i}{X_j - X_i}(x - X_i)
제법에 연루되면 오차를 고려해야 하기 때문에 번거롭기 때문에 분모를 지불하고 아래처럼 변형시켜야 한다.
(y - Y_i)(X_j - X_i) = (Y_j - Y_i)(x - X_i)
이 식의 변수 x와 y에서 각각 남은 1점의 좌표 Xk와 Yk를 대입할 때 방정식이 성립되면 3점은 일직선에 존재한다.
설치 예
실제 코드를 표시합니다.계산량은\mathcal{O}(N^3)입니다.
또한 각 변의 곱셈 중 가장 큰 값은 (2\times10^9)^2 = 4\times10^{18}이며, 이는 기호가 있는 64비트 정수의 최대치인 9223372036854775807보다 작기 때문에 넘침이 발생하지 않는다.
c.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int main() {
int64_t N;
std::cin >> N;
std::vector<int64_t> x(N);
std::vector<int64_t> y(N);
for (int64_t i = 0; i < N; i++) {
std::cin >> x.at(i) >> y.at(i);
}
int64_t count = 0;
for (int64_t i = 0; i < N; i++) {
for (int64_t j = i + 1; j < N; j++) {
for (int64_t k = j + 1; k < N; k++) {
if ((y.at(k) - y.at(i)) * (x.at(j) - x.at(i)) == (y.at(j) - y.at(i)) * (x.at(k) - x.at(i))) {
continue;
} else {
count++;
}
}
}
}
std::cout << count << std::endl;
return 0;
}
참고 문헌
↩︎
Reference
이 문제에 관하여(ABC224 C - Triangle? C++ 해답 예), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://zenn.dev/fjnkt98/articles/de5619c277770e텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
