AT1202Contest_i Convex Dombination

[problemUrl]: https://atcoder.jp/contests/DEGwer2023/tasks/1202Contest_i 平面上の $ N $ 個の相異なる格子点 $ (X_i,\ Y_i)\ (i\ =\ 1,\ 2,\ \dots,\ N) $ が与えられます． 各格子点 $ (X_i,\ Y_i) $ は整数の得点 $ P_i $ を持っています． これらの格子点から，以下の条件を満たすように好きな個数だけ選びます． このとき，選んだ格子点の得点の総和としてあり得る最大値を求めてください． **条件:** 選ばれた格子点の**凸結合**に**支配される**ような格子点は必ず選ばれている． すなわち，各 $ k\ =\ 1,\ 2,\ \dots,\ N $ について，以下を満たす $ N $ 個の**非負**実数の組 $ (\lambda_1,\ \lambda_2,\ \dots,\ \lambda_N) $ が存在するならば，格子点 $ (X_k,\ Y_k) $ は選ばれている． - $ \lambda_i\ >\ 0\ \implies\ {} $格子点 $ (X_i,\ Y_i) $ は選ばれている． - $ \sum_{i=1}^N\ \lambda_i\ =\ 1 $ - $ \sum_{i=1}^N\ \lambda_i\ X_i\ \geq\ X_k $ - $ \sum_{i=1}^N\ \lambda_i\ Y_i\ \geq\ Y_k $

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 200 $ - $ 1\ \leq\ X_i\ \leq\ 10^9\ (1\ \leq\ i\ \leq\ N) $ - $ 1\ \leq\ Y_i\ \leq\ 10^9\ (1\ \leq\ i\ \leq\ N) $ - $ (X_i,\ Y_i)\ \neq\ (X_j,\ Y_j)\ (i\ \neq\ j) $ - $ |P_i|\ \leq\ 10^7\ (1\ \leq\ i\ \leq\ N) $ ### Sample Explanation 1 $ (X_2,\ Y_2)\ =\ (4,\ 1) $ のみを選ぶのが最適です． $ (X_1,\ Y_1)\ =\ (1,\ 4) $ も選ぶ場合，たとえば $ \lambda_1\ =\ 0.4,\ \lambda_2\ =\ 0.6 $ とすると， \\\\\\\[ \\\\lambda\\\_1 + \\\\lambda\\\_2 = 0.4 + 0.6 = 1\\\\\\\\\\\[1mm\\\] \\\\lambda\\\_1 X\\\_1 + \\\\lambda\\\_2 X\\\_2 = 0.4 \\\\times 1 + 0.6 \\\\times 4 = 2.8 \\\\geq 2 = X\\\_3\\\\\\\\\\\[1mm\\\] \\\\lambda\\\_1 Y\\\_1 + \\\\lambda\\\_2 Y\\\_2 = 0.4 \\\\times 4 + 0.6 \\\\times 1 = 2.2 \\\\geq 2 = Y\\\_3 \\\\\\\] となるため，$ (X_3,\ Y_3)\ =\ (2,\ 2) $ も選ぶ必要があり，結果として損をします． ### Sample Explanation 2 すべての点を選ぶのが最適です． ### Sample Explanation 3 $ 1 $ つも選ばないのが最適な場合もあります．