結果

問題 No.461 三角形はいくつ？
ユーザー Guowen Rong
提出日時 2025-07-28 17:35:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 312 ms / 5,000 ms
コード長 1,831 bytes
コンパイル時間 2,100 ms
コンパイル使用メモリ 201,712 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-28 17:36:07
合計ジャッジ時間 7,656 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

 #include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define add(x, y) ((x + y >= mod) ? (x + y - mod) : (x + y))
#define dec(x, y) ((x - y < 0) ? (x - y + mod) : (x - y))
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef long double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 4040;
const db eps = 1e-18;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
ll ans = 0;
int n;
vector<db> V[3];
bool End;
int main(){
	n = read();
	for(int p, a, b, i = 1; i <= n; ++i){
		p = read(), a = read(), b = read();
		V[p].push_back((db)1.0 * a / (a + b));
	}
	for(int i = 0; i < 3; ++i)
	  sort(V[i].begin(), V[i].end());
	ans = n + 1;
	for(auto a : V[0]){
		for(auto b : V[1])
		  if(a + b > 1 + eps)
		    ++ans;
		for(auto b : V[2])
		  if(a + b > 1 + eps)
		    ++ans;		
	}
	for(auto a : V[1])
	  for(auto b : V[2])
	    if(a + b > 1 + eps)
	      ++ans;
	for(auto a : V[0]){
		for(auto b : V[1]){
			if(a + b < 1 - eps)
			  continue;
			db x = 1 - min(a, b);
			ans += V[2].end() - lower_bound(V[2].begin(), V[2].end(), x - eps);
			x = 2 - (a + b);
			ans -= lower_bound(V[2].begin(), V[2].end(), x + eps) - lower_bound(V[2].begin(), V[2].end(), x - eps);
		}
	}
	write(ans);
	//cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
	return 0;
}
0