d789 - 00920 - Sunny Mountains
題目描述
題目要求計算一連串山巔和山坳座標所構成的向陽山坡的總長度。給定一系列的 (x, y) 座標，其中 x 座標互不相同，最左邊的點的 x 座標為 0，最右邊的點的 y 座標為 0。需要計算陽光水平照射下，山坡的總長度。
解題思路
首先，將給定的座標按照 x 座標從小到大排序。然後，從第二個點開始，如果當前點的 y 座標大於前一個點的 y 座標，則計算從前一個點到當前點的山坡長度。山坡長度可以通過計算兩點之間的距離，並根據 y 座標的差值進行比例縮放得到。具體來說，如果當前點的 y 座標大於前一個點的 y 座標，則計算兩點之間的距離，並將其乘以 (當前點的 y 座標減去前一個點的 y 座標) / (當前點的 y 座標減去前一個點的 y 座標) 。將所有山坡長度加起來，即可得到總長度。
複雜度分析
- 時間複雜度: O(n log n)，主要來自於排序操作。其餘操作的時間複雜度為 O(n)。
- 空間複雜度: O(n)，用於儲存座標點。
程式碼
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
struct mn{
double x,y;
};
bool cmp(mn xx,mn yy){
if(xx.x>yy.x||(xx.x==yy.x&&xx.y>xx.y))return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int c,n;
cin >> c;
while(c--){
cin >> n;
double h=0,ans=0;
mn a[n];
for(int i=0;i<n;++i)
cin >> a[i].x >> a[i].y;
sort(a,a+n,cmp);
for(int i=1;i<n;++i)
if(a[i].y>h){
ans+=sqrt((a[i-1].x-a[i].x)*(a[i-1].x-a[i].x)+(a[i-1].y-a[i].y)*(a[i-1].y-a[i].y))*((a[i].y-h)/(a[i].y-a[i-1].y));
h=a[i].y;
}
printf("%.2lf\n",ans);
}
}