SPOJ.COM - Thuật toán bài QUADAREA - Maximal Quadrilateral Area

Đề bài:

Bạn đang cố gắng để xây dựng một ngôi nhà. Nhưng không may, hiện tại bạn chỉ có sẵn 4 tường với chiều dài lần lượt là a, b, c, d. Bạn muốn ngôi nhà của bạn là lớn nhất có thể. Vì vậy, bạn muốn biết diện tích lớn nhất có thể của những hình tứ giác mà bạn có thể xây từ 4 bức tường với chiều dài đó.

Đầu vào

Dòng đầu tiên chứa số nguyên T, 1 ≤ T ≤ 2,000, là số lượng test case. Mỗi test case chứa một dòng gồm 4 số thực: a, b, c, d, với 0 < a, b, c, d < 1,000. Chú ý rằng luôn luôn có thể tồn tại hình tứ giác với những độ dài trên, tức là tổng của 3 cạnh luôn lớn hơn cạnh còn lại.

Đầu ra

Mỗi test case, in ra một dòng là một số biểu diễn diện tích lớn nhất có thể. Kết quả được làm tròn 2 chữ số thập phân.

Ví dụ

Đầu vào:

2
1 2 1 2
0.5 0.5 0.5 0.5

Đầu ra:

2.00
0.25

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/QUADAREA/

Phân tích

• Theo như quan điểm của mình thì đây thực chất là một bài toán mẹo. Do đó mình sẽ xếp nó vào loạt bài sử dụng thuật toán tham lam Greedy.

• Thực tế, với một hình tứ giác có 4 cạnh xác định trước. Thì dù bạn có xoay nó như thế nào đi chăng nữa thì diện tích của nó cũng sẽ không thay đổi - là một giá trị duy nhất. Do đó, bạn chỉ cần tính diện tích bình thường. Mình áp dụng công thức Heron để tính diện tích tứ giác lồi.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);

	int T;
	cin >> T;
	for(int tc = 0; tc < T; tc++)
	{
		double a,b,c,d;
		cin >> a >> b >> c >> d;

		double p = (a + b + c + d) / 2;
		double S = sqrt((p-a)*(p-b)*(p-c)*(p-d));

		printf("%.2lf\n", S);
	}
	return 0;
}