Posted on 2010-08-12 11:19
MiYu 閱讀(681)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM ( 數(shù)學(xué)題/幾何 )
MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2036
題目描述:
改革春風(fēng)吹滿地
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5623 Accepted Submission(s): 2763
Problem Description
“ 改革春風(fēng)吹滿地,
不會(huì)AC沒關(guān)系;
實(shí)在不行回老家，
還有一畝三分地。
謝謝!（樂隊(duì)奏樂）”
話說部分學(xué)生心態(tài)極好，每天就知道游戲，這次考試如此簡單的題目，也是云里霧里，而且，還竟然來這么幾句打油詩。
好呀，老師的責(zé)任就是幫你解決問題，既然想種田，那就分你一塊。
這塊田位于浙江省溫州市蒼南縣靈溪鎮(zhèn)林家鋪?zhàn)哟?，多邊形形狀的一塊地，原本是linle 的，現(xiàn)在就準(zhǔn)備送給你了。不過，任何事情都沒有那么簡單，你必須首先告訴我這塊地到底有多少面積，如果回答正確才能真正得到這塊地。
發(fā)愁了吧？就是要讓你知道，種地也是需要AC知識(shí)的！以后還是好好練吧
Input
輸入數(shù)據(jù)包含多個(gè)測試實(shí)例，每個(gè)測試實(shí)例占一行，每行的開始是一個(gè)整數(shù)n(3<=n<=100)，它表示多邊形的邊數(shù)（當(dāng)然也是頂點(diǎn)數(shù)），然后是按照逆時(shí)針順序給出的n個(gè)頂點(diǎn)的坐標(biāo)（x1, y1, x2, y2 xn, yn）,為了簡化問題，這里的所有坐標(biāo)都用整數(shù)表示。
輸入數(shù)據(jù)中所有的整數(shù)都在32位整數(shù)范圍內(nèi)，n=0表示數(shù)據(jù)的結(jié)束，不做處理。
Output
對(duì)于每個(gè)測試實(shí)例，請(qǐng)輸出對(duì)應(yīng)的多邊形面積，結(jié)果精確到小數(shù)點(diǎn)后一位小數(shù)。
每個(gè)實(shí)例的輸出占一行。
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;
}