hdoj 2036 (计算几何，叉积求面积)
改革春风吹满地
**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24179 Accepted Submission(s): 12504
**
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
Author
lcy
Source
一个多边形。
n个定点按照逆时针方向给出..
求面积。
<span style="color: #008080;"> 1</span> <span style="color: #008000;">/*</span><span style="color: #008000;">************************************************************************
</span><span style="color: #008080;"> 2</span> <span style="color: #008000;"> > File Name: code/hdoj/2036.cpp
</span><span style="color: #008080;"> 3</span> <span style="color: #008000;"> > Author: 111qqz
</span><span style="color: #008080;"> 4</span> <span style="color: #008000;"> > Email: rkz2013@126.com
</span><span style="color: #008080;"> 5</span> <span style="color: #008000;"> > Created Time: 2015年11月06日 星期五 12时05分30秒
</span><span style="color: #008080;"> 6</span> <span style="color: #008000;"> ***********************************************************************</span><span style="color: #008000;">*/</span>
<span style="color: #008080;"> 7</span>
<span style="color: #008080;"> 8</span> #include<iostream>
<span style="color: #008080;"> 9</span> #include<iomanip>
<span style="color: #008080;">10</span> #include<cstdio>
<span style="color: #008080;">11</span> #include<algorithm>
<span style="color: #008080;">12</span> #include<cmath>
<span style="color: #008080;">13</span> #include<cstring>
<span style="color: #008080;">14</span> #include<<span style="color: #0000ff;">string</span>>
<span style="color: #008080;">15</span> #include<map>
<span style="color: #008080;">16</span> #include<<span style="color: #0000ff;">set</span>>
<span style="color: #008080;">17</span> #include<queue>
<span style="color: #008080;">18</span> #include<vector>
<span style="color: #008080;">19</span> #include<stack>
<span style="color: #008080;">20</span> #include<cctype>
<span style="color: #008080;">21</span> <span style="color: #0000ff;">#define</span> fst first
<span style="color: #008080;">22</span> <span style="color: #0000ff;">#define</span> lson l,m,rt<<1
<span style="color: #008080;">23</span> <span style="color: #0000ff;">#define</span> rson m+1,r,rt<<1|1
<span style="color: #008080;">24</span> <span style="color: #0000ff;">#define</span> ms(a,x) memset(a,x,sizeof(a))
<span style="color: #008080;">25</span> <span style="color: #0000ff;">using</span> <span style="color: #0000ff;">namespace</span><span style="color: #000000;"> std;
</span><span style="color: #008080;">26</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dx4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span>,<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span><span style="color: #000000;">};
</span><span style="color: #008080;">27</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> dy4[<span style="color: #800080;">4</span>]={<span style="color: #800080;">0</span>,-<span style="color: #800080;">1</span>,<span style="color: #800080;">1</span>,<span style="color: #800080;">0</span><span style="color: #000000;">};
</span><span style="color: #008080;">28</span> typedef <span style="color: #0000ff;">long</span> <span style="color: #0000ff;">long</span><span style="color: #000000;"> LL;
</span><span style="color: #008080;">29</span> <span style="color: #0000ff;">#define</span> sec second
<span style="color: #008080;">30</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> inf = <span style="color: #800080;">0x3f3f3f3f</span><span style="color: #000000;">;
</span><span style="color: #008080;">31</span> <span style="color: #0000ff;">const</span> <span style="color: #0000ff;">int</span> N=<span style="color: #800080;">105</span><span style="color: #000000;">;
</span><span style="color: #008080;">32</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> n;
</span><span style="color: #008080;">33</span> <span style="color: #0000ff;">struct</span><span style="color: #000000;"> point
</span><span style="color: #008080;">34</span> <span style="color: #000000;">{
</span><span style="color: #008080;">35</span> <span style="color: #0000ff;">double</span><span style="color: #000000;"> x,y;
</span><span style="color: #008080;">36</span> <span style="color: #000000;"> point(){}
</span><span style="color: #008080;">37</span> point(<span style="color: #0000ff;">double</span> _x,<span style="color: #0000ff;">double</span><span style="color: #000000;"> _y):
</span><span style="color: #008080;">38</span> x(_x),y(-<span style="color: #000000;">y){};
</span><span style="color: #008080;">39</span> <span style="color: #0000ff;">void</span><span style="color: #000000;"> input()
</span><span style="color: #008080;">40</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">41</span> scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%lf%lf</span><span style="color: #800000;">"</span>,&x;,&<span style="color: #000000;">y);
</span><span style="color: #008080;">42</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">43</span> <span style="color: #0000ff;">double</span><span style="color: #000000;"> det(point p)
</span><span style="color: #008080;">44</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">45</span> <span style="color: #0000ff;">return</span> x*p.y-y*<span style="color: #000000;">p.x;
</span><span style="color: #008080;">46</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">47</span> <span style="color: #000000;">};
</span><span style="color: #008080;">48</span> <span style="color: #0000ff;">struct</span><span style="color: #000000;"> polygon
</span><span style="color: #008080;">49</span> <span style="color: #000000;">{
</span><span style="color: #008080;">50</span> <span style="color: #000000;"> point p[N];
</span><span style="color: #008080;">51</span> <span style="color: #0000ff;">void</span><span style="color: #000000;"> input()
</span><span style="color: #008080;">52</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">53</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span> ; i < n ; i++<span style="color: #000000;">)
</span><span style="color: #008080;">54</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">55</span> <span style="color: #000000;"> p[i].input();
</span><span style="color: #008080;">56</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">57</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">58</span> <span style="color: #0000ff;">double</span><span style="color: #000000;"> getarea()
</span><span style="color: #008080;">59</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">60</span> <span style="color: #0000ff;">double</span> sum= <span style="color: #800080;">0</span><span style="color: #000000;"> ;
</span><span style="color: #008080;">61</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> i;
</span><span style="color: #008080;">62</span> <span style="color: #0000ff;">for</span> ( <span style="color: #0000ff;">int</span> i = <span style="color: #800080;">0</span> ; i < n ; i++<span style="color: #000000;"> )
</span><span style="color: #008080;">63</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">64</span> sum+=p[i].det(p[(i+<span style="color: #800080;">1</span>)%<span style="color: #000000;">n]);
</span><span style="color: #008080;">65</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">66</span> <span style="color: #0000ff;">return</span> fabs(sum)/<span style="color: #800080;">2</span><span style="color: #000000;">;
</span><span style="color: #008080;">67</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">68</span> <span style="color: #000000;">}pol;
</span><span style="color: #008080;">69</span> <span style="color: #0000ff;">int</span><span style="color: #000000;"> main()
</span><span style="color: #008080;">70</span> <span style="color: #000000;">{
</span><span style="color: #008080;">71</span> <span style="color: #000000;"> #ifndef ONLINE_JUDGE
</span><span style="color: #008080;">72</span> freopen(<span style="color: #800000;">"</span><span style="color: #800000;">in.txt</span><span style="color: #800000;">"</span>,<span style="color: #800000;">"</span><span style="color: #800000;">r</span><span style="color: #800000;">"</span><span style="color: #000000;">,stdin);
</span><span style="color: #008080;">73</span> <span style="color: #0000ff;">#endif</span>
<span style="color: #008080;">74</span> <span style="color: #0000ff;">while</span> (scanf(<span style="color: #800000;">"</span><span style="color: #800000;">%d</span><span style="color: #800000;">"</span>,&n;)!=EOF&&<span style="color: #000000;">n)
</span><span style="color: #008080;">75</span> <span style="color: #000000;"> {
</span><span style="color: #008080;">76</span> <span style="color: #000000;"> pol.input();
</span><span style="color: #008080;">77</span> printf(<span style="color: #800000;">"</span><span style="color: #800000;">%.1fn</span><span style="color: #800000;">"</span><span style="color: #000000;">,pol.getarea());
</span><span style="color: #008080;">78</span> <span style="color: #000000;"> }
</span><span style="color: #008080;">79</span>
<span style="color: #008080;">80</span>
<span style="color: #008080;">81</span>
<span style="color: #008080;">82</span> <span style="color: #000000;"> #ifndef ONLINE_JUDGE
</span><span style="color: #008080;">83</span> <span style="color: #000000;"> fclose(stdin);
</span><span style="color: #008080;">84</span> <span style="color: #0000ff;">#endif</span>
<span style="color: #008080;">85</span> <span style="color: #0000ff;">return</span> <span style="color: #800080;">0</span><span style="color: #000000;">;
</span><span style="color: #008080;">86</span> }
View Code