結果

問題 No.1999 Lattice Teleportation
コンテスト
ユーザー SSRS
提出日時 2022-07-01 22:47:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,959 bytes
コンパイル時間 2,655 ms
コンパイル使用メモリ 194,852 KB
実行使用メモリ 27,240 KB
最終ジャッジ日時 2024-11-26 06:23:09
合計ジャッジ時間 88,229 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 TLE * 1
other WA * 2 TLE * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const long long INF = 1000000000000000;
struct point{
  long long x, y;
  point(){
  }
  point(long long x, long long y): x(x), y(y){
  }
  point operator -(point P){
    return point(x - P.x, y - P.y);
  }
  bool operator ==(point P){
    return x == P.x && y == P.y;
  }
  bool operator <(point P){
    return x < P.x || x == P.x && y < P.y;
  }
};
__int128_t cross(point P, point Q){
  return (__int128_t) P.x * Q.y - (__int128_t) P.y * Q.x;
}
int main(){
  int N;
  cin >> N;
  vector<int> A, B;
  for (int i = 0; i < N; i++){
    int a, b;
    cin >> a >> b;
    if (a != 0 || b != 0){
      A.push_back(a);
      B.push_back(b);
    }
  }
  N = A.size();
  if (N == 0){
    cout << 1 << endl;
  } else {
    vector<tuple<long double, int, int>> V(N);
    for (int i = 0; i < N; i++){
      V[i] = make_tuple(atan2(B[i], A[i]), A[i], B[i]);
    }
    sort(V.begin(), V.end());
    A.clear();
    B.clear();
    A.push_back(get<1>(V[0]));
    B.push_back(get<2>(V[0]));
    for (int i = 1; i < N; i++){
      if (cross(point(get<1>(V[i - 1]), get<2>(V[i - 1])), point(get<1>(V[i]), get<2>(V[i]))) == 0){
        A.back() += get<1>(V[i]);
        B.back() += get<2>(V[i]);
      } else {
        A.push_back(get<1>(V[i]));
        B.push_back(get<2>(V[i]));
      }
    }
    N = A.size();
    __int128_t sx = 0, sy = 0;
    int l = 0, r = 0;
    vector<point> P;
    while (l < N){
      P.push_back(point(sx, sy));
      __int128_t sx2 = sx + A[r % N], sy2 = sy + B[r % N];
      if (r - l < N && sx * sx + sy * sy < sx2 * sx2 + sy2 * sy2){
        r++;
        sx = sx2;
        sy = sy2;
      } else {
        sx -= A[l];
        sy -= B[l];
        l++;
      }
    }
    sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());
    int cnt = P.size();
    stack<int> st1;
    st1.push(0);
    st1.push(1);
    for (int i = 2; i < cnt; i++){
      while (st1.size() >= 2){
        int a = st1.top();
        st1.pop();
        int b = st1.top();
        if (cross(P[i] - P[b], P[i] - P[a]) < 0){
          st1.push(a);
          break;
        }
      }
      st1.push(i);
    }
    stack<int> st2;
    st2.push(0);
    st2.push(1);
    for (int i = 2; i < cnt; i++){
      while (st2.size() >= 2){
        int a = st2.top();
        st2.pop();
        int b = st2.top();
        if (cross(P[i] - P[b], P[i] - P[a]) > 0){
          st2.push(a);
          break;
        }
      }
      st2.push(i);
    }
    vector<int> up, down;
    while (!st1.empty()){
      up.push_back(st1.top());
      st1.pop();
    }
    while (!st2.empty()){
      down.push_back(st2.top());
      st2.pop();
    }
    reverse(up.begin(), up.end());
    reverse(down.begin(), down.end());
    int cnt1 = up.size();
    int cnt2 = down.size();
    long long ans = 0;
    for (int i = 0; i < cnt1 - 1; i++){
      long long dx = P[up[i + 1]].x - P[up[i]].x;
      long long dy = P[up[i + 1]].y - P[up[i]].y;
      ans += P[up[i]].y % MOD * (dx % MOD) % MOD;
      for (int j = 0; j < dx; j++){
        long long q = j * dy;
        if (q >= 0){
          ans += q / dx;
        } else {
          ans -= (-q) / dx;
        }
      }
    }
    for (int i = 0; i < cnt2 - 1; i++){
      long long dx = P[down[i + 1]].x - P[down[i]].x;
      long long dy = P[down[i + 1]].y - P[down[i]].y;
      ans -= P[down[i]].y % MOD * (dx % MOD) % MOD;
      for (int j = 0; j < dx; j++){
        long long q = j * dy;
        if (q >= 0){
          ans -= q / dx;
        } else {
          ans += (-q) / dx;
        }
        if (q % dx == 0){
          ans++;
        }
      }
    }
    ans %= MOD;
    long long Xmx = P[N - 1].x;
    long long mx = -INF, mn = INF;
    for (int i = 0; i < N; i++){
      if (P[i].x == Xmx){
        mx = max(mx, P[i].y);
        mn = min(mn, P[i].y);
      }
    }
    ans += mx - mn + 1;
    ans += MOD;
    ans %= MOD;
    cout << ans << endl;
  }
}
0