※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 12742번 문제인 혼합물 (Small)이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/12742
12743번 문제와 같이 답이 유일함을 가정하겠다. 그리고 편의상
앞으로 만들 A의 양을
모든 조건을 만족하는
이 다각형의 꼭짓점들은 직선들
아래는 제출한 소스코드이다.
#include <iostream>
using namespace std;
typedef long long ll;
typedef long double ld;
ll N, X, Y;
ll A[200], B[200], W[200];
ld ans1, ans2, ans;
void solve11(int i) {
ld XX = (ld)W[i] / A[i];
ld YY = 0;
for (int k = 0; k < N; k++) {
if (XX * A[k] + YY * B[k] > W[k]) return;
}
ld val = XX * X + YY * Y;
if (val > ans) ans = val, ans1 = XX, ans2 = YY;
}
void solve12(int i) {
ld XX = 0;
ld YY = (ld)W[i] / B[i];
for (int k = 0; k < N; k++) {
if (XX * A[k] + YY * B[k] > W[k]) return;
}
ld val = XX * X + YY * Y;
if (val > ans) ans = val, ans1 = XX, ans2 = YY;
}
void solve2(int i, int j) {
if (A[i] * B[j] == A[j] * B[i]) return;
ld XX = (ld)(W[i] * B[j] - W[j] * B[i]) / (A[i] * B[j] - A[j] * B[i]);
ld YY = (ld)(W[j] * A[i] - W[i] * A[j]) / (A[i] * B[j] - A[j] * B[i]);
if (XX < 0 || YY < 0) return;
for (int k = 0; k < N; k++) {
if (XX * A[k] + YY * B[k] > W[k]) return;
}
ld val = XX * X + YY * Y;
if (val > ans) ans = val, ans1 = XX, ans2 = YY;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> X >> Y;
for (int i = 0; i < N; i++) cin >> A[i];
for (int i = 0; i < N; i++) cin >> B[i];
for (int i = 0; i < N; i++) cin >> W[i];
for (int i = 0; i < N; i++) {
solve11(i);
solve12(i);
for (int j = i + 1; j < N; j++) {
solve2(i, j);
}
}
cout << fixed;
cout.precision(2);
cout << ans << '\n' << ans1 << ' ' << ans2;
}
'BOJ' 카테고리의 다른 글
[BOJ 25917 // C++] Prime Arrangement (0) | 2024.05.06 |
---|---|
[BOJ 18231 // C++] 파괴된 도시 (0) | 2024.05.05 |
[BOJ 11895 // C++] 속이기 (0) | 2024.05.03 |
[BOJ 12843 // C++] 복수전공 (0) | 2024.05.02 |
[BOJ 24292 // C++] РАЗДЕЛЯЙ и ВЛАДЕЙ (1) | 2024.05.01 |