結果

問題 No.461 三角形はいくつ?
ユーザー vjudge1
提出日時 2025-07-25 22:03:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,289 bytes
コンパイル時間 1,740 ms
コンパイル使用メモリ 168,884 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-25 22:03:30
合計ジャッジ時間 6,791 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 15 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N=4010;
const int mod=1e9+7;
const double eps=1e-7;
int n;
int ans;
vector<double>v[3];
map<double,int>M;
signed main(){
	// ios::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
	// freopen("triangle.in","r",stdin);
	// freopen("triangle.out","w",stdout);
	cin>>n;
	for(int i=0;i<3;i++)v[i].push_back(0);
	for(int i=1;i<=n;i++){
		int d,x,y;
		cin>>d>>x>>y;
		v[d].push_back((double)y/(double)(x+y));
	}
	for(int i=0;i<v[0].size();i++){
		for(int j=0;j<v[1].size();j++){
			if(v[0][i]+v[1][j]>1.0)continue;
			int id1=upper_bound(v[2].begin(),v[2].end(),1.0-v[0][i])-v[2].begin();
			int id2=upper_bound(v[2].begin(),v[2].end(),1.0-v[1][j])-v[2].begin();
			int id=min(id1,id2);
			bool fl=0;
			int L=lower_bound(v[2].begin(),v[2].end(),1.0-v[0][i]-v[1][j])-v[2].begin();
			int R=upper_bound(v[2].begin(),v[2].end(),1.0-v[0][i]-v[1][j])-v[2].begin();
			if(L<R)fl=1;//??
			ans+=id-(int)fl;
			// for(int k=0;k<v[2].size();k++){
			// 	double sum=v[0][i]+v[1][j]+v[2][k];
			// 	if(sum==1.0)continue;
			// 	if(v[0][i]+v[1][j]<=1.0&&v[0][i]+v[2][k]<=1.0&&v[1][j]+v[2][k]<=1.0)ans++;
			// }
		}
	}
	cout<<ans<<"\n";
	return 0;
}
/*
????
?
?????
????????
?????naive?O(n^3)
???
*/
0