agc036a Triangle

ベクトルの存在を完全に忘れていた・・・

A - Triangle

一点を$0,0$に固定出来そうなのはわかる。　残りの二点をどうするかだけど、ベクトルの内積と三角形の面積の関係を使えば方向性は分かる。

みるのはここ

【応用】ベクトルの内積と三角形の面積 | なかけんの数学ノート

x3,y3を0,0に固定したとして。

$ \frac{S}{2} = |{x_1y_2 - x_2y_1}|$ が成立する。　

問題の制約上、$\frac{S}{2}$は必ず整数になることが保証されます。

さて、後は$x_1,x_2,y_1,y_2$を求めることがありますが、このままでは$(10^9)^4$通りあるのです。壊れるね。

ここでよく考えると、$x_1$を$10^9$を$x_2$を$1$に固定することができます。

考え方

$\frac{S}{2}$を$10^9$で割った商をp,余りをqとする。

$\frac{S}{2} = (10^9)*p + q$

式変形をすると、

$\frac{S}{2} = (10^9)*(p+1) + ( q - 10^9) $

ここで、$(10^9)*(p+1)$ は明らかに正の値であり、$( q - 10^9)$は明らかに負の値なのでこれらを$y_2,y_1$に設定してターンエンド！

S=ll(1e18)の時は別途対応が必要なのでなんとかする必要がありますのでなんとかしようね(WA)

提出 #15504899 - AtCoder Grand Contest 036

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    ll S;
    cin >> S;
    if(S == ll(1e18)) {
        cout << "0 0 0 1000000000 1000000000 0" << endl;
        return;
    }
    ll p = S/(ll)INF;
    ll q = S%(ll)INF;
    cout << 0 << " " << 0 << " " << ll(INF);
    cout << " " << ll(INF-q) << " " << 1 << " " << ll(p+1) << endl;
}

int main() {
    solve();
    return 0;
}