sdnu 1334 Jason's Water Problem【计算几何-多边形面积的计算】【负数取模】

迈不过友情╰ 2021-11-10 23:54 276阅读 0赞

## 1334.Jason's Water Problem ##

Time Limit: 1000 MS    Memory Limit: 32768 KB  
Total Submission(s):  [128][]    Accepted Submission(s):  [23][]

### Description ###

Calculus is the first lesson Jason had. It is tedious, so an interesting idea occurred to Jason. He took out his mobile phone and open the HDUOJ and found a water problem. He said to himself, “I must solve this f\*\*king easy water problem in ten minutes! ”.

You were invited to compete with him online. Don’t be defeated.

### Input ###

Multiple test cases, Each test first contains an integer *N(3<=N<=100000)** *indicating the number of vertices of the polygon. The *i**-**th* of the following *N*lines contains two integers *xi* and *y**i* *(**0<=**x**i**,y**i<=**10**^**9)* separated by a blank. *(x**i**,y**i**)* is the *i**-**th* vertex of the polygon, and *(x**1**,y**1**),...,(x**n**,y**n**)* will be in counterclockwise order.

### Output ###

For each test case, output a number as the answer which is the area of the polygon be multiplied by 2. In case the answer is greater than 1000000006, please modulo the answer with 1000000007.

### Sample Input ###

3
    0 0
    1 0
    0 1
    4
    0 0
    1 0
    1 1
    0 1

### Sample Output ###

1
    2

### Hint ###

### Source ###

[2015-2016\_SDNU\_ACM-ICPC\_Selection\_Match\_Round\_1][2015-2016_SDNU_ACM-ICPC_Selection_Match_Round_1]

错的代码：

1 #include<bits/stdc++.h>
     2 #define ll long long
     3 using namespace std;
     4 const ll mod=1000000007;
     5 struct point
     6 {
     7     ll x,y;
     8 }a[100050];
     9 ll calc(point c,point d)
    10 {
    11     return c.x*d.y-d.x*c.y;
    12 }
    13 int main()
    14 {
    15     int n;
    16     while(scanf("%d",&n)!=EOF)
    17     {
    18         for(int i=1;i<=n;i++)
    19         {
    20             scanf("%lld %lld",&a[i].x,&a[i].y);
    21         }
    22         ll ans=0;
    23         a[n+1]=a[1];
    24         for(int i=2;i<=n+1;i++)
    25         {
    26             ans=(ans+calc(a[i-1],a[i])%mod)%mod;
    27         }
    28         cout<<ans<<'\n';
    29     }
    30 }

ac的代码：

1 #include<bits/stdc++.h>
     2 #define ll long long
     3 using namespace std;
     4 const ll mod=1000000007;
     5 struct point
     6 {
     7     ll x,y;
     8 }a[100050];
     9 ll calc(point c,point d)
    10 {
    11     return (c.x*d.y-d.x*c.y);
    12 }
    13 int main()
    14 {
    15     int n;
    16     while(scanf("%d",&n)!=EOF)
    17     {
    18         for(int i=1;i<=n;i++)
    19         {
    20             scanf("%lld %lld",&a[i].x,&a[i].y);
    21         }
    22         a[n+1]=a[1];
    23         ll ans=0;
    24         for(int i=2;i<=n+1;i++)
    25         {
    26             ans=(ans+calc(a[i-1],a[i])%mod+mod)%mod;
    27         }
    28         cout<<ans<<'\n';
    29     }
    30 }

负数取余的公式为 （a%mod+mod）%mod  （orz好笨啊）

原引某博客的图

多边形的面积计算，多边形每个边两个端点跟原点组成一系列三角形，它们的面积有正负，所面积之和就是多边形的面积。   
![这里写图片描述][20161022161236842]

这里选取的端点p为原点（逃）

转载于:https://www.cnblogs.com/guanwen769aaaa/p/11281240.html

[128]: http://www.acmicpc.sdnu.edu.cn/status/list?pid=1334
[23]: http://www.acmicpc.sdnu.edu.cn/status/list?pid=1334&type=10
[2015-2016_SDNU_ACM-ICPC_Selection_Match_Round_1]: http://www.acmicpc.sdnu.edu.cn/problem/search?type=source&content=2015-2016_SDNU_ACM-ICPC_Selection_Match_Round_1
[20161022161236842]: /images/20211109/9e13e3b08d814cc5b48c3d96e08f4c07.png