題意：對于題目給的點，x固定，而與x組合的y可以任意交換，求如何安置y可使這些點組成線段下面的面積最大，最大面積是多少
分析：可以發(fā)現(xiàn)Xn-Xn-1的越大那么乘以y越大，所以我們只需求出，然后ΔX越大的數(shù)和y越大的數(shù)相乘在除以2就是結果，通過畫圖很容易得出結論
? ? ? ? ?但是還有一個問題就是，對于i=0,i=n-1，Yi只乘以了一遍，而對于0<i<n的區(qū)間，每個Yi都乘以了兩遍
? ? ? ? ?所以在求ΔX時候，當i=0，ΔX=X1-X0，當i=n-1時，ΔX=Xn-1-Xn-2，而對于0<i<n，ΔX=Xi+1-xi-1;
? ? ? ? ?這樣就能確保每個y每個都可以被乘以了兩次。
? ? ? ? ?（對于兩邊的區(qū)間Y不僅被乘以了1次，而且是最小的兩個值放在了兩邊）
#include<stdio.h>
#include
<
string
.h>
#include
<math.h>
#include
<algorithm>
using
namespace
std;
const
int
MN=
1100
;
double
x[MN],y[MN],r[MN];
bool
cmp(
double
a,
double
b)
{
return
a<
b;
}
int
main()
{
int
i,j,n;
double
sum;
int
T;
scanf(
"
%d
"
,&
T);
while
(T--
)
{
sum
=
0
;
scanf(
"
%d
"
,&
n);
for
(i=
0
;i<n;i++
)
scanf(
"
%lf%lf
"
,&x[i],&
y[i]);
sort(x,x
+
n,cmp);
sort(y,y
+
n,cmp);
for
(i=
0
;i<n-
1
;i++
)
{
if
(i==
0
) r[i]=x[i+
1
]-
x[i];
else
r[i]=x[i+
1
]-x[i-
1
];
}
r[i]
=x[i]-x[i-
1
];
sort(r,r
+
n,cmp);
for
(i=
0
;i<n;i++
)
{
sum
+=r[i]*
y[i];
}
printf(
"
%.1lf\n
"
,sum/
2
);
}
return
0
;
}
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
