結果

問題 No.947 ABC包囲網
コンテスト
ユーザー aruudo
提出日時 2026-09-11 11:31:31
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 3 ms / 2,000 ms
+ 448µs
コード長 2,010 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,493 ms
コンパイル使用メモリ 352,900 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2026-09-11 11:31:38
合計ジャッジ時間 6,314 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h> 

using i64 = long long; 
using u64 = unsigned long long; 
using u32 = unsigned; 

using u128 = unsigned __int128; 
using i128 = __int128; 

struct point2d {
public:
	int x, y;
	point2d() : x(0), y(0) {};
	point2d(int x_, int y_) : x(x_), y(y_) {};
	point2d operator-() const {
		return point2d(-x, -y);
	}
	int quadrant() const {
		if (y == 0) return x > 0 ? 0 : 4;
		if (x == 0) return y > 0 ? 2 : 6;
		if (y > 0) return x > 0 ? 1 : 3;
		return x > 0 ? 7 : 5;
	}
	bool operator==(const point2d& p) const {
		return x == p.x && y == p.y;
	}
	bool operator!=(const point2d& p) const {
		return x != p.x || y != p.y;
	}
	bool operator<(const point2d& p) const {
		int qa = quadrant(), qb = p.quadrant();
		if (qa != qb) return qa < qb;
		return 1LL * x * p.y > 1LL * y * p.x;
	}
};

void solve() {
	int N; std::cin >> N;

	std::vector<point2d> P(N);
	std::vector<point2d> pd;
	for(int i = 0; i < N; i ++) {
		std::cin >> P[i].x >> P[i].y;
		int g = std::gcd(std::abs(P[i].x), std::abs(P[i].y));
		P[i].x /= g; P[i].y /= g;
		pd.push_back(P[i]);
		pd.push_back(- P[i]);
	}
	std::sort(pd.begin(), pd.end());
	pd.erase(std::unique(pd.begin(), pd.end()), pd.end());
	int M = (int)pd.size() / 2;

	std::vector<int> seq(2 * M);
	for(int i = 0; i < N; i ++) {
		int ptr = std::lower_bound(pd.begin(), pd.end(), P[i]) - pd.begin();
		seq[ptr] ++;
	}

	int sump = 0, sumq = 0;
	for(int i = 0; i < M; i ++) sump += seq[i];
	sumq = sump + seq[M];

	i64 ans = 0;
	for(int i = 0; i < 2 * M; i ++) {
		ans += 1LL * sumq * (sumq - 1) * (sumq - 2) - 1LL * sump * (sump - 1) * (sump - 2);
		sump += seq[i < M ? i + M : i - M] - seq[i];
		sumq += seq[i < M - 1 ? i + M + 1 : i - M + 1] - seq[i];
	}

	for(int i = 0; i < M; i ++) ans -= seq[i] * seq[i + M] * (seq[i] + seq[i + M] - 2) * 3;

	std::cout << (1LL * N * (N - 1) * (N - 2) - ans) / 6;

} 

int main() { 
	std::ios::sync_with_stdio(false); 
	std::cin.tie(nullptr); 

	int T = 1; 
	//std::cin >> T; 

	while (T--) { 
		solve(); 
	} 
	return 0; 
}
0