比赛 ZLXOI2015Day2 评测结果 AAAAAAWWWW
题目名称 妹妹的饼干 最终得分 60
用户昵称 lyxin65 运行时间 0.003 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2015-10-30 20:45:36
显示代码纯文本
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long LL;
  6.  
  7. const int maxn = 1030;
  8.  
  9. struct Point
  10. {
  11. int x, y;
  12. Point operator - (const Point &a) const { return (Point){x - a.x, y - a.y}; }
  13. }p[maxn];
  14.  
  15. inline LL cross(const Point &a, const Point &b)
  16. {
  17. return a.x * b.y - a.y * b.x;
  18. }
  19.  
  20. inline LL cross(const Point &a, const Point &b, const Point &c)
  21. {
  22. return cross(b - a, c - a);
  23. }
  24.  
  25. int n;
  26.  
  27. void input()
  28. {
  29. scanf("%d", &n);
  30. for(int i = 0; i < n; ++i)
  31. scanf("%d%d", &p[i].x, &p[i].y);
  32. }
  33.  
  34. //pick: S = a + b/2 - 1
  35. //a = S - b/2 + 1
  36.  
  37. void solve()
  38. {
  39. LL S = 0, b = 0;
  40. for(int i = 0; i+2 < n; ++i)
  41. S += cross(p[0], p[i+1], p[i+2]);
  42. S = abs(S);
  43. for(int i = 0; i < n; ++i)
  44. {
  45. Point q = p[(i+1)%n] - p[i];
  46. b += __gcd(abs(q.x), abs(q.y));
  47. }
  48. LL a = S - b + 2;
  49. cout << a / 2 << endl;
  50. }
  51.  
  52. int main()
  53. {
  54. freopen("sistercookies.in", "r", stdin);
  55. freopen("sistercookies.out", "w", stdout);
  56. input();
  57. solve();
  58. fclose(stdin);
  59. fclose(stdout);
  60. return 0;
  61. }