v 0. Pasted by slipstak2 as cpp at 2011-01-06 17:25:30 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 12.
  2. // 12D. Точки в многоугольнике [polygonp]
  3. // ibelyaev: 03Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8.  
  9. using namespace std;
  10. typedef long long INT;
  11. struct point
  12. {
  13.     INT x,y;
  14.     void input()
  15.     {
  16.         scanf("%lld %lld", &x, &y);
  17.     }
  18. };
  19. vector<point> mas;
  20. int n;
  21. void input()
  22. {
  23.     cin>>n;
  24.     mas.resize(n);
  25.     for (int i=0;i<n;i++)
  26.         mas[i].input();
  27. }
  28. inline INT _abs(INT a)
  29. {
  30.     if (a < 0)
  31.         return -a;
  32.     return a;
  33. }
  34. INT Square(point &a, point &b, point &c)
  35. {
  36.     return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
  37. }
  38. INT gcd (INT a, INT b)
  39. {
  40.     return b?gcd(b,a%b):a;
  41. }
  42. INT findBP()
  43. {
  44.     INT res = 0;
  45.     for (int i=0;i<n;i++)
  46.     {
  47.         INT dx = _abs(mas[i].x - mas[(i+1)%n].x);
  48.         INT dy = _abs(mas[i].y - mas[(i+1)%n].y);
  49.         res += gcd(dx,dy);
  50.     }
  51.     return res;
  52.  
  53. }
  54. void solve()
  55. {
  56.     INT S = 0;
  57.    
  58.     for (int i=1;i<n-1;i++)
  59.         S += Square(mas[0],mas[i],mas[i+1]);
  60.    
  61.     S = _abs(S) / 2;
  62.  
  63.     INT BorderPoints = findBP();
  64.    
  65.     INT InsidePoints  = S - BorderPoints/2 + 1;
  66.     cout<<InsidePoints;
  67. }
  68. int main()
  69. {
  70.     freopen("input.txt","r",stdin);
  71.     freopen("output.txt","w",stdout);
  72.  
  73.     input();
  74.     solve();
  75.     return 0;
  76. }


Editing is locked.