5070 : 선형 계획법
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$ 개의 선형 부등식 $c_i x + d_i y \le e_i$ 와 $x, y \ge 0$ 을 모두 만족하는 영역 내에서, $ax + by$ 의 최댓값을 구하십시오.
[제약 조건]
• $1 \le N \le 500$
• $1 \le a_i,b_i,c_i \le 10^9$
• $x+y$ 가 최대가 될 때, $x$ 와 $y$ 는 모두 양의 실수입니다.
[제약 조건]
• $1 \le N \le 500$
• $1 \le a_i,b_i,c_i \le 10^9$
• $x+y$ 가 최대가 될 때, $x$ 와 $y$ 는 모두 양의 실수입니다.
입력 설명
첫째 줄에 $N$ 이 주어집니다.
출력 설명
최댓값을 출력하십시오. 절대 오차 또는 상대 오차가 $10^{-6}$ 이내이면 정답으로 인정됩니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2
1 1
1 2 4
2 1 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2.6666666667도움
모든 부등식의 교점들과 축과의 교점들을 조사하십시오.