提出 #31046558

---

ソースコード 拡げる

//https://atcoder.jp/contests/abc248/tasks/abc248_e
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
ll gcd(ll a, ll b) { return a ? gcd(b % a, a) : b; }
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














pair<ll, ll> normalization(ll up, ll down, bool slope = true) {
	if (down < 0) {
		up *= -1;
		down *= -1;
	}

	if (down == 0) {
		if (slope) up = 1;
	}
	else {
		ll g = gcd(abs(up), down);
		up /= g;
		down /= g;
	}

	return {up, down};
}

int N, K; ll X[301], Y[301];

tuple<ll, ll, ll, ll> getParameter(int a, int b) {
	ll dx = X[a] - X[b];
	ll dy = Y[a] - Y[b];

	tie(dy, dx) = normalization(dy, dx);

	// ya = dy * xa / dx + b
	// b = (ya * dx - dy * xa) / dx

	ll bup = Y[a] * dx - dy * X[a];
	ll bdown = dx;

	tie(bup, bdown) = normalization(bup, bdown, false);
	return { dy, dx, bup, bdown };
}

void _main() {
	cin >> N >> K;
	rep(i, 0, N) cin >> X[i] >> Y[i];

	if (K == 1) {
		cout << "Infinity" << endl;
		return;
	}

	map<tuple<ll, ll, ll, ll>, int> cnt;

	rep(a, 0, N) rep(b, a + 1, N) cnt[getParameter(a, b)]++;

	map<int, int> rcomb;
	rep(n, K, N + 1) rcomb[n * (n - 1) / 2] = 1;

	int ans = 0;
	fore(p, cnt) ans += rcomb[p.second];
	cout << ans << endl;
}





/* ///////////////////////// writeup1 start
///////////////////////// writeup2 start
幾何問題。
以下解法、非常に面倒なので、別の解法があるかも…

## （解法に移る前に）

以下のケースでちょっとはまったので、WAではまってる人はこれを確認してみるといいかも。

```
6 3
1 3
1 4
1 5
6 10
6 11
6 12
```

## Infinityのとき

K=1の場合はどのような場合でも無数に解が存在する。
K=1の時は、Infinityと出して終了しよう。

## どういった方針を取るか

今回は点を通る直線を題材とした問題であるが、直線は少なくとも2点があれば作成することができる。
逆に3点あると複数の直線ができてしまったり、色々面倒なので、2点を使った直線から解法が導けないか考えてみる。

ここから思考が飛ぶが、試行錯誤がこの間にあったと考えてほしい…

例えば、任意のa番目の点とb番目の点（a＜b）について直線を列挙していったときに、
同一直線状に3点ある直線は3回現れる。点abcを通っていれば、ab,ac,bcの列挙時に出てくる。
同一直線状に4点ある直線は6回現れる。点abcdを通っていれば、ab,ac,ad,bc,bd,cdの列挙時に出てくる。
つまり、同一直線についてはn点あれば、C(n,2)回現れることになる。（関数Cは二項係数）

よって、
cnt[ (ある直線を表す何らかの情報）] := 任意の2頂点を選んだときにある直線が何通りあるか
というのが計算できれば、その個数から直線に何個点があるかを逆算することができる。

## 『ある直線を表す何らかの情報』

自分はこれに傾きと切片を使った。
入力値が[-10^9,10^9]だったので、doubleは落ちそうな気配があり、有理数でどちらも保持する道を選んだ。
傾きをdx/dy, 切片をbup/bdownという風に有理数で定義して、2つの分数について正規化をすれば、
(dx, dy, bup, bdown)の数の組がとある直線を一意に表してくれるようになる。
以下の関数を作って計算している。

getParameter(a,b) := 2頂点a,bを通る直線を表す(dx, dy, bup, bdown)を返す

具体的には
https://blog.hamayanhamayan.com/entry/2018/09/30/203639
っぽいことをやる。

> a = (ya - yb) / (xa - xb)
> b = (xa * yb - xb * ya) / (xa - xb)

という感じで分数を作って、ソースコードにあるnormalization関数みたいに有理化する感じである。
(xa - xb)が0になるときが注意で、傾きは分子を1にするが、切片は分子をそのままにしている。
縦の直線なので、傾きと切片を定義はできないのだが、便宜上このようにして直線を同一視させている。
///////////////////////// writeup2 end */

提出情報

ジャッジ結果