NEFU 652 Triangle：面積法判斷點在三角形內部

問題描述

給定三角形三頂點 (x1,y1), (x2,y2), (x3,y3) 和測試點 (l,r)，判斷測試點是否嚴格在三角形內部（邊上不算）。輸入多組，以全 0 結束。

面積法原理

三角形面積 S = |(x1y2 - x2y1) + (x2y3 - x3y2) + (x3y1 - x1y3)| / 2。
測試點 P 與三頂點構成三個子三角形，面積和 S1+S2+S3。
若 P 在內部，則 S1+S2+S3 = S 且每個 Si > 0（不在邊上）。
若 P 在邊上，某 Si = 0；若在外部，和 > S。

代碼實現（整數座標，避免浮點）

int area2(int x1, int y1, int x2, int y2, int x3, int y3) {
    return abs(x1*y2 - x2*y1 + x2*y3 - x3*y2 + x3*y1 - x1*y3); // 2倍面積
}
int main() {
    int x[3], y[3], l, r;
    while (cin >> x[0] >> y[0] >> x[1] >> y[1] >> x[2] >> y[2] >> l >> r) {
        if (x[0]==0 && x[1]==0 && x[2]==0 && y[0]==0 && y[1]==0 && y[2]==0 && l==0 && r==0) break;
        int S = area2(x[0],y[0], x[1],y[1], x[2],y[2]);
        int S1 = area2(x[0],y[0], x[1],y[1], l,r);
        int S2 = area2(x[0],y[0], l,r, x[2],y[2]);
        int S3 = area2(l,r, x[1],y[1], x[2],y[2]);
        if (S == S1+S2+S3 && S1 && S2 && S3) cout << "YES\n";
        else cout << "NO\n";
    }
}

優勢與注意

• 整數運算無精度問題，座標範圍內不溢出（用 long long 更保險）。
• 判斷條件 S1 && S2 && S3 確保點不在邊上。
• 適用於任意簡單多邊形內部判斷（射線法更通用），但三角形面積法最簡潔。