[PKU1654]Area

题目就是求封闭图形的面积。

如果一个封闭图形按照一定顺序的点集P={(x1, y1), (x2, y2), …, (xn, yn)}，那么其面积就是几个向量积的和：S=|0.5*((x1, y1)×(x2, y2)+(x2, y2)×(x3, y3)+…+(xn, yn)×(x1, y1))|。因为题目是给定一条路径生成多边形，所以根据读入顺序就保证了边的顺序，就不需要进行极角排序了。 注意，这题没必要用，因为小数位只有可能为.5，只需要根据S奇偶性特判就好了 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <cstdlib>
#include <iostream>
#define x first
#define y second
using namespace std;

typedef pair<long long, long long> Point;
int T, now;
Point a[2], O(0, 0);
inline long long CrossProduct(const Point& A, const Point& B, const Point& C, const Point& D)
{
  const long long x1 = B.x-A.x, y1 = B.y-A.y;
  const long long x2 = D.x-C.x, y2 = D.y-C.y;
  return x1*y2-y1*x2;
}
int main()
{
  ios::sync_with_stdio(false);
  cin >> T;
  while (T--)
  {
    a[now = 0] = make_pair(0, 0);
    long long ans = 0;
    char c;
    while (cin >> c, c != '5')
    {
      long long x = a[now].x, y = a[now].y;
      if (c == '9' || c == '6' || c == '3') ++x;
      if (c == '7' || c == '4' || c == '1') --x;
      if (c == '7' || c == '8' || c == '9') ++y;
      if (c == '1' || c == '2' || c == '3') --y;
      a[now ^= 1] = make_pair(x, y);
      ans += CrossProduct(O, a[now^1], O, a[now]);
    }
    if (ans < 0)
      ans = -ans;
    if (ans&1)
      cout << ((ans-1)>>1) << ".5" << endl;
    else
      cout << (ans>>1) << endl;
  }
}

Comments