TriAB

Điểm: 0,50 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trên hệ trục tọa độ ~OXY~, cho hai tập điểm nguyên ~A~ và ~B~ lần lượt gồm ~n~ và ~m~ điểm.

Tập điểm ~A~ gồm ~a_1,a_2,...,a_n~ và tập điểm ~B~ gồm ~b_1,b_2,...,b_m~.

Gọi ~f(i,j,k)~ là số điểm ~b_x~ nằm trong tam giác được tạo bởi ba đểm ~(a_i,a_j,a_k)~.

Tính ~\sum_{i=1}^{n-2} \sum_{j=i+1}^{n-1} \sum_{k=j+1}^n f(i,j,k)~.

Input

Dòng đầu tiên gồm hai số nguyên dương ~n,m~ ~(1 \le n,m \le 300)~;
~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~a_i~ ~(|x_i|,|y_i| \le 10^9)~.
~m~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~x_i,y_i~ miêu tả tọa độ ~(x_i,y_i)~ của điểm ~a_i~ ~(|x_i|,|y_i| \le 10^9)~.

Dữ liệu đảm bảo tọa độ ~x~ của mọi điểm là phân biệt và không có bộ ba điểm nào thẳng hàng.

Output

In ra kết quả của bài toán.

Sample Input 1

Sample Output 1

Bình luận

Hãy đọc nội quy trước khi bình luận.

WeoBuXCS đã bình luận lúc 16, Tháng 9, 2025, 13:24

brute force như này vẫn sai. Cái cách hiểu đề bài của mình có đúng không các bạn?

#include <iostream>
#include <cmath>
using namespace std;

struct Point {
    int x, y;
};
long double dien_tich_tam_giac(Point& A, Point& B, Point& C)
{
    long double s = 0.5 * abs(1LL * A.x * (B.y - C.y) + 1LL * B.x * (C.y - A.y) + 1LL * C.x * (A.y - B.y));
    return s;
}
bool is_in_triangle(Point& A, Point& B, Point& C, Point& D)
{
    long double S_ABC = dien_tich_tam_giac(A, B, C);
    long double S_ADB = dien_tich_tam_giac(A, D, B);
    long double S_ADC = dien_tich_tam_giac(A, D, C);
    long double S_BDC = dien_tich_tam_giac(B, D, C);
    if(S_ADB + S_ADC + S_BDC == S_ABC)
    {
        return true;
    }
    return false;
}
int main() {
    Point A[301], B[301];
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> A[i].x >> A[i].y;
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> B[i].x >> B[i].y;
    }
    unsigned long long ans = 0;
    for(int i = 1; i <= n - 2; i++)
    {
        for(int j = i + 1; j <= n - 1; j++)
        {
            for(int k = j + 1; k <= n; k++)
            {
                for(int index = 1; index <= m; index++)
                {
                    if(is_in_triangle(A[i], A[j], A[k], B[index]))
                    {
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

0

WeoBuXCS đã bình luận lúc 16, Tháng 9, 2025, 13:23

"m dòng sau, dòng thứ i gồm hai số nguyên xi, yi miêu tả tọa độ của điểm a[i]" ?