🌟

AGC 036 | A - Triangle

2020/12/18に公開

競プロ

座標

tech

問題

解法

$X_3 = 0, Y_3 = 0$ としたときの三角形の面積が $\frac{S}{2}$ に等しいので以下のようになる。

\frac{X_1 Y_2 - X_2 Y_1}{2} = \frac{S}{2}

$1 \leq S \leq 10^{18}$ と $0 \leq X_1,Y_1,X_2,Y_2,X_3,Y_3 \leq 10^9$ が条件なので $X_1 = 10^9, X_2 = 1$ と置くと以下のようになる。

10^{9} Y_2 - Y_1 = S

10^{9} Y_2 = S + Y_1

$0 \leq Y_1$ なので以下となる

10^{9} Y_2 \geq S

Y_2 \geq \frac{S}{10^9}

$Y_2$ は整数なので以下となる。

Y_2 \geq \lceil \frac{S}{10^9} \rceil

$Y_2$ が求まれば $Y_1$ も求まる。

コード

実装時のTips

long doubleを使うと浮動小数点で誤差がでる可能性があるので割り切れるかどうかでceilを実現している

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

void output(vector<ll> v) {
  for (int i = 0; i < 6; i++) {
    cout << v[i];
    if (i != 5) {
      cout << " ";
    }
  }
  cout << endl;
}

int main() {
  ll s;
  cin >> s;
  ll a = 1e9;
  vector<ll> v = {
      a,  // x1
      0,  // y1
      1,  // x2
      0,  // y2
      0,  // x3
      0,  // y3
  };
  // 残りのy1とy2を求める
  ll y2 = 0;
  if (s % a == 0) {
    y2 = s / a;
  } else {
    y2 = s / a + 1;
  }
  ll y1 = a * y2 - s;
  v[1] = y1;
  v[3] = y2;
  output(v);
}

AGC 036 | A - Triangle

問題

解法

コード

参考

Discussion