結果

問題 No.461 三角形はいくつ？
ユーザー vjudge1
提出日時 2025-07-25 21:37:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,662 bytes
コンパイル時間 1,747 ms
コンパイル使用メモリ 181,924 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-07-25 21:37:18
合計ジャッジ時間 3,645 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 3 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4010;
const int mod=1e9+7;
int n;
int ans;
vector<pair<int,int> >v[3];
map<pair<int,int>,int>cnt[3];
bool operator < (pair<int,int>a,pair<int,int>b){
	return a.first*b.second<b.first*a.second;
}
signed main(){
	// ios::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int d,x,y;
		cin>>d>>x>>y;
		int g=__gcd(x,y);
		x/=g;y/=g;
		v[d].push_back(make_pair(x,y));
		cnt[d][make_pair(x,y)]++;
	}
	sort(v[0].begin(),v[0].end());
	sort(v[1].begin(),v[1].end());
	sort(v[2].begin(),v[2].end());
	ans=1;
	ans+=(int)v[0].size();
	ans+=(int)v[1].size();
	ans+=(int)v[2].size();
	ans+=(int)v[0].size()*(int)v[1].size();
	ans+=(int)v[0].size()*(int)v[2].size();
	ans+=(int)v[1].size()*(int)v[2].size();
	ans+=(int)v[0].size()*(int)v[1].size()*(int)v[2].size();
	//????
	for(int i=0;i<v[0].size();i++){
		int x=v[0][i].first;
		int y=v[0][i].second;
		ans-=cnt[1][make_pair(y,x)];
	}
	for(int i=0;i<v[0].size();i++){
		int x=v[0][i].first;
		int y=v[0][i].second;
		ans-=cnt[2][make_pair(y,x)];
	}
	for(int i=0;i<v[1].size();i++){
		int x=v[1][i].first;
		int y=v[1][i].second;
		ans-=cnt[2][make_pair(y,x)];
	}
	//??????
	for(int i=0;i<v[0].size();i++){
		int x=v[0][i].first;
		int y=v[0][i].second;
		int id=upper_bound(v[1].begin(),v[1].end(),make_pair(x,y))-v[1].begin();
		id=(int)v[1].size()-id;
		ans-=id*(v[2].size()+1);
	}
	for(int i=0;i<v[0].size();i++){
		int x=v[0][i].first;
		int y=v[0][i].second;
		int id=upper_bound(v[2].begin(),v[2].end(),make_pair(x,y))-v[2].begin();
		id=(int)v[2].size()-id;
		ans-=id*(v[1].size()+1);
	}
	for(int i=0;i<v[1].size();i++){
		int x=v[1][i].first;
		int y=v[1][i].second;
		int id=upper_bound(v[2].begin(),v[2].end(),make_pair(x,y))-v[2].begin();
		id=(int)v[2].size()-id;
		ans-=id*(v[0].size()+1);
	}
	// for(int i=0;i<v[0].size();i++){
	// 	int x=v[0][i].first;
	// 	int y=v[0][i].second;
	// 	int id1=upper_bound(v[1].begin(),v[1].end(),make_pair(x,y))-v[1].begin();
	// 	int id2=upper_bound(v[2].begin(),v[2].end(),make_pair(x,y))-v[2].begin();
	// 	ans+=min(id1,id2);
	// }
	// for(int i=0;i<v[0].size();i++){
	// 	int x=v[0][i].first;
	// 	int y=v[0][i].second;
	// 	int id1=upper_bound(v[0].begin(),v[0].end(),make_pair(x,y))-v[0].begin();
	// 	int id2=upper_bound(v[2].begin(),v[2].end(),make_pair(x,y))-v[2].begin();
	// 	ans+=min(id1,id2);
	// }
	// for(int i=0;i<v[1].size();i++){
	// 	int x=v[1][i].first;
	// 	int y=v[1][i].second;
	// 	int id1=upper_bound(v[1].begin(),v[1].end(),make_pair(x,y))-v[1].begin();
	// 	int id2=upper_bound(v[2].begin(),v[2].end(),make_pair(x,y))-v[2].begin();
	// 	ans+=min(id1,id2);
	// }
	//????
	int res=0;
	for(int i=0;i<v[0].size();i++){
		int x=v[0][i].first;
		int y=v[0][i].second;
		if(x<y)continue;
		int xx=2*y;
		int yy=x-y;
		int g=__gcd(xx,yy);
		xx/=g;yy/=g;
		// cerr<<"!"<<xx<<" "<<yy<<"\n";
		res+=cnt[1][make_pair(x,y)]*cnt[2][make_pair(xx,yy)];
		res+=cnt[2][make_pair(x,y)]*cnt[1][make_pair(xx,yy)];
	}
	for(int i=0;i<v[1].size();i++){
		int x=v[1][i].first;
		int y=v[1][i].second;
		if(x<y)continue;
		int xx=2*y;
		int yy=x-y;
		int g=__gcd(xx,yy);
		xx/=g;yy/=g;
		res+=cnt[0][make_pair(x,y)]*cnt[2][make_pair(xx,yy)];
		res+=cnt[2][make_pair(x,y)]*cnt[0][make_pair(xx,yy)];
	}
	for(int i=0;i<v[2].size();i++){
		int x=v[2][i].first;
		int y=v[2][i].second;
		if(x<y)continue;
		int xx=2*y;
		int yy=x-y;
		int g=__gcd(xx,yy);
		xx/=g;yy/=g;
		res+=cnt[0][make_pair(x,y)]*cnt[1][make_pair(xx,yy)];
		res+=cnt[1][make_pair(x,y)]*cnt[0][make_pair(xx,yy)];
	}
	// cerr<<res<<"\n";
	res/=2;
	ans-=res;
	cout<<ans<<"\n";
	return 0;
}
/*

*/
0