結果
問題 |
No.461 三角形はいくつ?
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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) ??? */