結果

問題 No.461 三角形はいくつ？
ユーザー vjudge1
提出日時 2025-07-26 21:17:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 331 ms / 5,000 ms
コード長 1,808 bytes
コンパイル時間 1,434 ms
コンパイル使用メモリ 170,028 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-26 21:17:48
合計ジャッジ時間 9,510 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 41
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:10:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   10 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
main.cpp:14:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |         scanf("%d%d%d",&p,&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=4005;
const long double eps=1e-17;
int n;
vector<long double> t[3];
ll ans;
int main(){
    scanf("%d",&n);
    t[0].push_back(1);t[1].push_back(1);t[2].push_back(1);
    for(int i=1;i<=n;++i){
        int p,a,b;
        scanf("%d%d%d",&p,&a,&b);
        t[p].push_back(a/(long double)(a+b));
    }
    sort(t[0].begin(),t[0].end());
    sort(t[1].begin(),t[1].end());
    sort(t[2].begin(),t[2].end());
    for(long double l0:t[0]){
        for(long double l1:t[1]){
            long double mx=max(1-l0,1-l1);
            long double jd=2-l0-l1;
            if(jd>1+eps)continue;
            int it1=lower_bound(t[2].begin(),t[2].end(),mx-eps)-t[2].begin();
            int it2=lower_bound(t[2].begin(),t[2].end(),jd-eps)-t[2].begin();
            ans+=t[2].size()-it1;
            if(fabs(t[2][it2]-jd)<eps)ans--;
        }
    }
    for(long double l0:t[0]){
        for(long double l1:t[2]){
            long double mx=max(1-l0,1-l1);
            long double jd=2-l0-l1;
            if(jd>1+eps)continue;
            int it1=lower_bound(t[1].begin(),t[1].end(),mx-eps)-t[1].begin();
            int it2=lower_bound(t[1].begin(),t[1].end(),jd-eps)-t[1].begin();
            ans+=t[1].size()-it1;
            if(fabs(t[1][it2]-jd)<eps)ans--;
        }
    }
    for(long double l0:t[1]){
        for(long double l1:t[2]){
            long double mx=max(1-l0,1-l1);
            long double jd=2-l0-l1;
            if(jd>1+eps)continue;
            int it1=lower_bound(t[0].begin(),t[0].end(),mx-eps)-t[0].begin();
            int it2=lower_bound(t[0].begin(),t[0].end(),jd-eps)-t[0].begin();
            ans+=t[0].size()-it1;
            if(fabs(t[0][it2]-jd)<eps)ans--;
        }
    }
    printf("%lld\n",ans/3);
    return 0;
}
0