SGU 251 Polymania：幾何構造題

題目大意

平面上 n (3≤n≤8) 個點，每點有未知座標和正整數權值 R_i，且 R_{n-1}=R_n。要求構造一組座標，使任意三點形成的三角形面積等於三點權值之和。

分析與構造

利用最後兩個權值相等的點作為基準。構造需滿足：無三點共線；座標形式特定。對 n=3,4 分情況討論，通過解線性方程組確定座標。關鍵條件：n>4 無解；n=4 時若 R1+R2 ≠ R3+R4 則需 R1=R2 等條件。

代碼 (C++)

#include <cstdio>
#include <cmath>
using namespace std;
const double EPS = 1e-8;
int n; double R[5];

int main() {
    scanf("%d", &n);
    if (n > 4) { puts("NO"); return 0; }
    for (int i = 1; i <= n; i++) scanf("%lf", &R[i]);
    if (n == 4) {
        if (fabs(R[1]+R[2]-R[3]-R[4]) > EPS) {
            if (fabs(R[1]-R[2]) > EPS) puts("NO");
            else {
                double x3 = -10, x4 = 10;
                double y = (R[1]+R[3]+R[4])*2/(x4-x3);
                double x = (R[1]+R[2]+R[3])*2/y;
                puts("YES");
                printf("%.4lf %.4lf\n", -x/2, y);
                printf("%.4lf %.4lf\n",  x/2, y);
                printf("%.4lf 0.0000\n", x3);
                printf("%.4lf 0.0000\n", x4);
            }
        } else {
            double x3 = -10, x4 = 10;
            double y1 = (R[1]+R[3]+R[4])*2/(x4-x3);
            double y2 = -(R[2]+R[3]+R[4])*2/(x4-x3);
            puts("YES");
            printf("0.0000 %.4lf\n", y1);
            printf("0.0000 %.4lf\n", y2);
            printf("%.4lf 0.0000\n", x3);
            printf("%.4lf 0.0000\n", x4);
        }
    } else { // n == 3
        double x2 = -10, x3 = 10;
        double y1 = (R[1]+R[2]+R[3])*2/(x3-x2);
        puts("YES");
        printf("0.0000 %.4lf\n", y1);
        printf("%.4lf 0.0000\n", x2);
        printf("%.4lf 0.0000\n", x3);
    }
    return 0;
}