---
# System prepended metadata

title: UCUP 2-26

---

###### tags: ucup

# UCUP 2-26



---
## --------------Solved------------------

## L
yo

## K
yo

## D
si

## E
yo

## C
si

## G
si


## F
yo

## J
si

## I
原点を中心とする半径Rの円と、その内部にあるN点が与えられる
あなたは円の中に1点だけ追加できる
N+1点の凸包の面積を最大化

誰か氏～～
TODO: @koheim

## H
yo

## B
si

## A
yo

x_min / x_max / y_min / y_maxのそれぞれはO(N)本の折れ線になっている

よってtはO(N)個の区間にわけられて、その区間の中では|x_max - x_min|, |y_max - y_min|はすべて直線 => 算数


時間区切られた中で
x0 -> x1, y0 -> y1 と一次関数的に変化するとする
dx := x1-x0, dy := y1-y0
f(t) := (x0 + tdx)(y0 + tdy)
```
ans = min(f(0),f(1))
if(dx != 0 && dy != 0){
t = -(x0/dx + y0/dy)/2
if(0 <= t && t <= 1) chmin(ans,f(t))
}
```