Posted on 2010-08-12 11:19
MiYu 閱讀(685)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 數學題/幾何 )
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2036
題目描述:
改革春風吹滿地
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5623 Accepted Submission(s): 2763
Problem Description
“ 改革春風吹滿地,
不會AC沒關系;
實在不行回老家，
還有一畝三分地。
謝謝!（樂隊奏樂）”
話說部分學生心態極好，每天就知道游戲，這次考試如此簡單的題目，也是云里霧里，而且，還竟然來這么幾句打油詩。
好呀，老師的責任就是幫你解決問題，既然想種田，那就分你一塊。
這塊田位于浙江省溫州市蒼南縣靈溪鎮林家鋪子村，多邊形形狀的一塊地，原本是linle 的，現在就準備送給你了。不過，任何事情都沒有那么簡單，你必須首先告訴我這塊地到底有多少面積，如果回答正確才能真正得到這塊地。
發愁了吧？就是要讓你知道，種地也是需要AC知識的！以后還是好好練吧
Input
輸入數據包含多個測試實例，每個測試實例占一行，每行的開始是一個整數n(3<=n<=100)，它表示多邊形的邊數（當然也是頂點數），然后是按照逆時針順序給出的n個頂點的坐標（x1, y1, x2, y2 xn, yn）,為了簡化問題，這里的所有坐標都用整數表示。
輸入數據中所有的整數都在32位整數范圍內，n=0表示數據的結束，不做處理。
Output
對于每個測試實例，請輸出對應的多邊形面積，結果精確到小數點后一位小數。
每個實例的輸出占一行。
Sample Input
3 0 0 1 0 0 1
4 1 0 0 1 -1 0 0 -1
0
Sample Output
0.5
2.0
題目分析:
模板題. 直接用 多邊形面積公式 : S = 1/2 * abs( ∑(xiyi+1 – xi+1yi) )
代碼如下:
#include <iostream>
#include <cmath>
using namespace std;
typedef struct point{
int x, y;
}point;
point polygon[101];
double areaGmty ( int num )
{
double area = 0;
for ( int i = 0; i < num; ++ i )
{
area += ( polygon[i].x * polygon[(i+1)%num].y ) - (polygon[(i+1)%num].x * polygon[i].y);
}
return area;
}
int main ()
{
int N;
while ( scanf ( "%d",&N ), N )
{
for ( int i = 0; i != N; ++ i )
{
scanf ( "%d%d", &polygon[i].x,&polygon[i].y );
}
double area = areaGmty ( N ) / 2.0;
printf ( "%.1lf\n",area );
}
return 0;
}