fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int MOD = 998244353;
  7.  
  8. int mul(int x, int y) {
  9.     return (ll) x * y % MOD;
  10. }
  11.  
  12. int add(int x, int y) {
  13.     x += y;
  14.     if (x >= MOD) x -= MOD;
  15.     return x;
  16. }
  17.  
  18. int sub(int x, int y) {
  19.     x -= y;
  20.     if (x < 0) x += MOD;
  21.     return x;
  22. }
  23.  
  24. int fast(int x, ll y = MOD - 2) {
  25.     int res = 1;
  26.     for ( ; y > 0; y >>= 1, x = mul(x, x)) {
  27.         if (y & 1) {
  28.             res = mul(res, x);
  29.         }
  30.     }
  31.     return res;
  32. }
  33.  
  34. const int MX = 5e6 + 9;
  35.  
  36. int pw[MX];
  37.  
  38. void init() {
  39.     pw[0] = 1;
  40.     for (int i = 1; i < MX; i++) {
  41.         pw[i] = mul(pw[i - 1], 2);
  42.     }
  43. }
  44.  
  45. #define x first
  46. #define y second
  47.  
  48. using pii = pair<int, int>;
  49.  
  50. int cross(pii a, pii b) {
  51.     return a.x * b.y - b.x * a.y;
  52. }
  53.  
  54. void solve() {
  55.     int n;
  56.     cin >> n;
  57.  
  58.     vector<pii> p(n);
  59.     for (int i = 0; i < n; i++) {
  60.         cin >> p[i].x >> p[i].y;
  61.         ++p[i].x;
  62.         ++p[i].y;
  63.     }
  64.  
  65.     int area = 0;
  66.     for (int i = 0, j = 1; i < n; i++, j++, j -= (j < n ? 0 : n)) {
  67.         area += cross(p[i], p[j]);
  68.     }
  69.  
  70.     if (area < 0) {
  71.         reverse (p.begin(), p.end());
  72.     }
  73.  
  74.     const int N = 2e3 + 9;
  75.     vector<vector<int>> vis(N, vector<int>(N));
  76.  
  77.     const vector<int> dx = {-1, 0, 1, 0};
  78.     const vector<int> dy = {0, -1, 0, 1};
  79.  
  80.     vector<pii> layer;
  81.     for (int i = 0, j = 1; i < n; i++, j++, j -= (j < n ? 0 : n)) {
  82.         if (p[i].x == p[j].x) {
  83.             if (p[i].y < p[j].y) {
  84.                 for (int k = p[i].y; k <= p[j].y; k++) {
  85.                     if (k != p[j].y) {
  86.                         layer.push_back({p[i].x, k});
  87.                     }
  88.                     vis[p[i].x + 1][k] = 1;
  89.                 }
  90.             } else {
  91.                 for (int k = p[i].y; k >= p[j].y; k--) {
  92.                     if (k != p[j].y) {
  93.                         layer.push_back({p[i].x, k});
  94.                     }
  95.                     vis[p[i].x - 1][k] = 1;
  96.                 }
  97.             }
  98.         } else {
  99.             if (p[i].x < p[j].x) {
  100.                 for (int k = p[i].x; k <= p[j].x; k++) {
  101.                     if (k != p[j].x) {
  102.                         layer.push_back({k, p[i].y});
  103.                     }
  104.                     vis[k][p[i].y - 1] = 1;
  105.                 }
  106.             } else {
  107.                 for (int k = p[i].x; k >= p[j].x; k--) {
  108.                     if (k != p[j].x) {
  109.                         layer.push_back({k, p[i].y});
  110.                     }
  111.                     vis[k][p[i].y + 1] = 1;
  112.                 }
  113.             }
  114.         }
  115.     }
  116.  
  117.     for (auto [x, y] : layer) {
  118.         vis[x][y] = 1;
  119.     }
  120.  
  121.     vector<int> cnt(MX);
  122.     for (int k = 0; layer.size() > 0; k++) {
  123.         cnt[k] = layer.size();
  124.         vector<pii> nw;
  125.         for (auto [x, y] : layer) {
  126.             for (int d = 0; d < 4; d++) {
  127.                 int nx = x + dx[d], ny = y + dy[d];
  128.                 if (vis[nx][ny]) {
  129.                     continue;
  130.                 }
  131.                 vis[nx][ny] = 1;
  132.                 nw.push_back({nx, ny});
  133.             }
  134.         }
  135.         swap(layer, nw);
  136.     }
  137.  
  138.     int ans = 0;
  139.     for (int d = 1; d < MX; d++) {
  140.         cnt[d] += cnt[d - 1];
  141.         int res = sub(pw[cnt[d]], pw[cnt[d - 1]]);
  142.         ans = add(ans, mul(res, d));
  143.     }
  144.  
  145.     ans = mul(ans, fast(pw[cnt[MX - 1]] - 1));
  146.  
  147.     cout << ans << "\n";
  148. }
  149.  
  150. int main() {
  151.     ios_base::sync_with_stdio(false);
  152.     cin.tie(nullptr);
  153.  
  154.     init();
  155.  
  156.     int t = 1;
  157. //    cin >> t;
  158.  
  159.     while (t--) {
  160.         solve();
  161.     }
  162.  
  163.     return 0;
  164. }
  165.  
  166. /*
  167.  
  168.  
  169.  
  170. */
Success #stdin #stdout 0.05s 58148KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/qcXTPm
language:
C++14 (gcc 8.3)
created:
14 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!