数格点

C++14(g++5.4) 解法, 执行用时: 30ms, 内存消耗: 620K, 提交时间: 2019-02-02 23:45:36

# include <bits/stdc++.h>
using namespace std;
 
#define y2 __mstczuo__y2
const int maxn = 1200;
 
typedef __int128 ll;
//typedef long long ll;
 
ll x[maxn], y[maxn];
ll X[maxn], Y[maxn];
int u, v, n;
 
void init() {
 int a, b;
 long long mx = 0, my = 0;
 scanf("%d%d%d%d%d", &u, &v, &a, &b, &n);
 for(int i = 0; i < n; ++i) {
  long long X, Y; scanf("%lld%lld", &X, &Y);
  x[i] = X - a; y[i] = Y - b;
  mx = max(mx, a-X);
  my = max(my, b-Y);
 }
 mx = mx + (u - mx % u);
 my = my + (v - my % v);
 for(int i = 0; i < n; ++i) {
  x[i] += mx;
  y[i] += my;
 }
}
 
//sum_{i=1}^{n} (bi+c)/a
ll solve(ll n,ll a,ll b,ll c) {
 if(n<=0)return 0; ll ret = 0, t;
 if (c < 0) { t = (a - 1 - c) / a; ret -= t * n; c += a * t; }
 if (b < 0) { t = (a - 1 - b) / a; ret -= t * n * (n + 1) / 2; b += a * t; }
 if (c / a) ret += (c / a) * n, c %= a;
 if (b / a) ret += (b / a) * n * (n + 1) / 2, b %= a;
 ll n2 = (c + b * n) / a;
 return ret + n2 * (n + 1) - solve(n2, b, a, b-c-1);
}
 
#define pre(i) ((i)==0)?(n-1):((i)-1)
#define nxt(i) ((i)==n-1)?(0):((i)+1)
 
ll calc_upper_part() {
 ll ret = 0;
 int p = 0;
 for(int i = 1; i < n; ++i)
  if(x[i] < x[p] || (x[i] == x[p] && y[i] > y[p])) p = i;
 int cc = 0;
 X[cc] = x[p], Y[cc++] = y[p];
 if((long double)(y[pre(p)] - y[p]) * (x[nxt(p)] - x[p]) > (long double)(y[nxt(p)] - y[p]) * (x[pre(p)] - x[p])) {
  while(x[pre(p)] > x[p]) {
   p = pre(p);
   X[cc] = x[p], Y[cc++] = y[p];
  }
 } else {
  while(x[nxt(p)] > x[p]) {
   p = nxt(p);
   X[cc] = x[p], Y[cc++] = y[p];
  }
 }
 int last = (X[0] - 1) / u;
 for(int i = 1; i < cc; ++i) {
  ll x1 = X[i-1], y1 = Y[i-1], x2 = X[i], y2 = Y[i];
  ll cur = x2 / u;
  if (cur == last) continue;
  ll A = v * (x2 - x1), B = (y2 - y1) * u, C = y1 * (x2 - x1) - x1 * (y2 - y1);
  ret -= solve(last, A, B, C);
  ret += solve(cur, A, B, C);
  last = cur;
 }
 return ret;
}
 
ll calc_lower_part() {
 ll ret = 0;
 int p = 0;
 for(int i = 1; i < n; ++i)
  if(x[i] < x[p] || (x[i] == x[p] && y[i] < y[p])) p = i;
 int cc = 0;
 X[cc] = x[p], Y[cc++] = y[p];
 if((long double)(y[pre(p)] - y[p]) / (x[pre(p)] - x[p]) < (long double)(y[nxt(p)] - y[p]) / (x[nxt(p)] - x[p])) {
  while(x[pre(p)] > x[p]) {
   p = pre(p);
   X[cc] = x[p], Y[cc++] = y[p];
  }
 } else {
  while(x[nxt(p)] > x[p]) {
   p = nxt(p);
   X[cc] = x[p], Y[cc++] = y[p];
  }
 }
 int last = (X[0] - 1) / u;
 for(int i = 1; i < cc; ++i) {
  ll x1 = X[i-1], y1 = Y[i-1], x2 = X[i], y2 = Y[i];
  ll cur = x2 / u;
  if (cur == last) continue;
  ll A = v * (x2 - x1), B = (y2 - y1) * u, C = y1 * (x2 - x1) - x1 * (y2 - y1);
  ret -= solve(last, A, B, C - 1);
  ret += solve(cur, A, B, C - 1);
  last = cur;
 }
 return ret;
}
 
int main() {
 int T; scanf("%d", &T);
 while(T--) {
  init();
  ll ans = calc_upper_part() - calc_lower_part();
  cout << (long long) ans << endl;
 }
}

C++11(clang++ 3.9) 解法, 执行用时: 31ms, 内存消耗: 608K, 提交时间: 2019-01-07 18:59:59

# include <bits/stdc++.h>
using namespace std;

#define y2 __mstczuo__y2
const int maxn = 1200;

typedef __int128 ll;
//typedef long long ll;

ll x[maxn], y[maxn];
ll X[maxn], Y[maxn];
int u, v, n;

void init() {
 int a, b;
 long long mx = 0, my = 0;
 scanf("%d%d%d%d%d", &u, &v, &a, &b, &n);
 for(int i = 0; i < n; ++i) {
  long long X, Y; scanf("%lld%lld", &X, &Y);
  x[i] = X - a; y[i] = Y - b;
  mx = max(mx, a-X);
  my = max(my, b-Y);
 }
 mx = mx + (u - mx % u);
 my = my + (v - my % v);
 for(int i = 0; i < n; ++i) {
  x[i] += mx;
  y[i] += my;
 }
}

//sum_{i=1}^{n} (bi+c)/a
ll solve(ll n,ll a,ll b,ll c) {
 if(n<=0)return 0; ll ret = 0, t;
 if (c < 0) { t = (a - 1 - c) / a; ret -= t * n; c += a * t; }
 if (b < 0) { t = (a - 1 - b) / a; ret -= t * n * (n + 1) / 2; b += a * t; }
 if (c / a) ret += (c / a) * n, c %= a;
 if (b / a) ret += (b / a) * n * (n + 1) / 2, b %= a;
 ll n2 = (c + b * n) / a;
 return ret + n2 * (n + 1) - solve(n2, b, a, b-c-1);
}

#define pre(i) ((i)==0)?(n-1):((i)-1)
#define nxt(i) ((i)==n-1)?(0):((i)+1)

ll calc_upper_part() {
 ll ret = 0;
 int p = 0;
 for(int i = 1; i < n; ++i) 
  if(x[i] < x[p] || (x[i] == x[p] && y[i] > y[p])) p = i;
 int cc = 0;
 X[cc] = x[p], Y[cc++] = y[p];
 if((long double)(y[pre(p)] - y[p]) * (x[nxt(p)] - x[p]) > (long double)(y[nxt(p)] - y[p]) * (x[pre(p)] - x[p])) {
  while(x[pre(p)] > x[p]) {
   p = pre(p);
   X[cc] = x[p], Y[cc++] = y[p];
  }
 } else {
  while(x[nxt(p)] > x[p]) {
   p = nxt(p);
   X[cc] = x[p], Y[cc++] = y[p];
  }
 }
 int last = (X[0] - 1) / u;
 for(int i = 1; i < cc; ++i) {
  ll x1 = X[i-1], y1 = Y[i-1], x2 = X[i], y2 = Y[i];
  ll cur = x2 / u;
  if (cur == last) continue;
  ll A = v * (x2 - x1), B = (y2 - y1) * u, C = y1 * (x2 - x1) - x1 * (y2 - y1);
  ret -= solve(last, A, B, C);
  ret += solve(cur, A, B, C);
  last = cur;
 }
 return ret;
}

ll calc_lower_part() {
 ll ret = 0;
 int p = 0;
 for(int i = 1; i < n; ++i) 
  if(x[i] < x[p] || (x[i] == x[p] && y[i] < y[p])) p = i;
 int cc = 0;
 X[cc] = x[p], Y[cc++] = y[p];
 if((long double)(y[pre(p)] - y[p]) / (x[pre(p)] - x[p]) < (long double)(y[nxt(p)] - y[p]) / (x[nxt(p)] - x[p])) {
  while(x[pre(p)] > x[p]) {
   p = pre(p);
   X[cc] = x[p], Y[cc++] = y[p];
  }
 } else {
  while(x[nxt(p)] > x[p]) {
   p = nxt(p);
   X[cc] = x[p], Y[cc++] = y[p];
  }
 }
 int last = (X[0] - 1) / u;
 for(int i = 1; i < cc; ++i) {
  ll x1 = X[i-1], y1 = Y[i-1], x2 = X[i], y2 = Y[i];
  ll cur = x2 / u;
  if (cur == last) continue;
  ll A = v * (x2 - x1), B = (y2 - y1) * u, C = y1 * (x2 - x1) - x1 * (y2 - y1);
  ret -= solve(last, A, B, C - 1);
  ret += solve(cur, A, B, C - 1);
  last = cur;
 }
 return ret;
}

int main() {
 int T; scanf("%d", &T);
 while(T--) {
  init();
  ll ans = calc_upper_part() - calc_lower_part();
  cout << (long long) ans << endl;
 }
}

详情