結果

問題 No.461 三角形はいくつ？
ユーザー vjudge1
提出日時 2025-07-27 20:37:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 302 ms / 5,000 ms
コード長 2,381 bytes
コンパイル時間 2,218 ms
コンパイル使用メモリ 205,372 KB
実行使用メモリ 8,296 KB
最終ジャッジ日時 2025-07-27 20:38:07
合計ジャッジ時間 7,683 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
bool st;
using namespace std;
template<typename T>istream&operator>>(istream&I,vector<T>&v){for(auto&i:v)I>>i;return I;}
template<typename T>ostream&operator<<(ostream&O,vector<T> v){for(auto i:v)O<<i<<' ';return O;}
string TMP,STR;
stringstream CIN;
void read_all(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#ifdef debug
	cerr<<"----------------------------------- START -----------------------------------\n";
	while(getline(cin,TMP))STR+=TMP,STR+='\n';
	CIN.str(STR);
	cerr<<"\n--------------------------------- INPUT END ---------------------------------\n";
#endif
}
#ifdef debug
#define cin CIN
#endif
namespace AC{
const long double eps=1e-18;
int n;
int p[400010],a[400010],b[400010];
vector<long double>v[3];
int ret;
void solve(){
	string s;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>p[i]>>a[i]>>b[i];
		v[p[i]].push_back((long double)1.0*a[i]/(a[i]+b[i]));
	}
	for(int i=0;i<3;i++)sort(all(v[i]));
	int ret=n+1;
	for(auto&r:v[0]){
		for(auto&r2:v[1])if(r+r2>1+eps)ret++;
		for(auto&r2:v[2])if(r+r2>1+eps)ret++;
	}
	for(auto&r:v[1])for(auto&r2:v[2])if(r+r2>1+eps)ret++;
	for(auto&r:v[0])for(auto&r2:v[1]){
		if(r+r2<1-eps)continue;
		long double hoge=1-min(r,r2);
		ret+=v[2].end()-lower_bound(all(v[2]),hoge-eps);
		hoge=2-(r+r2);
		ret-=lower_bound(all(v[2]),hoge+eps)-lower_bound(all(v[2]),hoge-eps);
	}
	cout<<ret<<endl;
}
}
bool ed;
signed main(){
	chrono::steady_clock::time_point St=chrono::steady_clock::now();
	read_all();
	chrono::steady_clock::time_point ST=chrono::steady_clock::now();
	int t=1;
	//cin>>t;
	while(t--)AC::solve();
	chrono::steady_clock::time_point ED=chrono::steady_clock::now();
	cerr<<setprecision(3)<<fixed<<"\n\n------------------------------------ END ------------------------------------\n"<<"Total Time   : "<<left<<setw(10)<<chrono::duration_cast<chrono::milliseconds>(ED-St).count()<<" \tms\n"<<"Real  Time   : "<<left<<setw(10)<<chrono::duration_cast<chrono::milliseconds>(ED-ST).count()<<" \tms\n"<<"             : "<<left<<setw(10)<<chrono::duration_cast<chrono::microseconds>(ED-ST).count()<<" \t?s\n\n"<<"Total Memory : "<<left<<setw(10)<<(&ed-&st)/1048576.0<<" \tMB\n"<<"               "<<left<<setw(10)<<(&ed-&st)/1024.0<<" \tKB\n"<<"               "<<left<<setw(10)<<(&ed-&st)<<" \tByte\n";
}
0