結果

問題 No.1144 Triangles
ユーザー hotman78hotman78
提出日時 2020-07-24 18:30:20
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 2,225 bytes
コンパイル時間 2,479 ms
コンパイル使用メモリ 80,564 KB
実行使用メモリ 62,992 KB
最終ジャッジ日時 2023-09-18 16:09:15
合計ジャッジ時間 30,946 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 120 ms
55,540 KB
testcase_01 AC 120 ms
56,628 KB
testcase_02 AC 122 ms
56,000 KB
testcase_03 AC 125 ms
56,004 KB
testcase_04 AC 2,009 ms
61,840 KB
testcase_05 AC 1,825 ms
62,068 KB
testcase_06 AC 1,937 ms
62,548 KB
testcase_07 WA -
testcase_08 AC 1,815 ms
61,728 KB
testcase_09 AC 123 ms
55,760 KB
testcase_10 AC 124 ms
55,868 KB
testcase_11 AC 126 ms
55,980 KB
testcase_12 AC 124 ms
55,696 KB
testcase_13 AC 124 ms
55,640 KB
testcase_14 AC 1,737 ms
61,720 KB
testcase_15 AC 1,813 ms
62,992 KB
testcase_16 AC 1,794 ms
62,328 KB
testcase_17 AC 1,864 ms
61,948 KB
testcase_18 AC 1,815 ms
59,992 KB
testcase_19 AC 426 ms
61,712 KB
testcase_20 AC 242 ms
60,436 KB
testcase_21 AC 244 ms
59,740 KB
testcase_22 AC 1,957 ms
62,328 KB
testcase_23 AC 483 ms
61,668 KB
testcase_24 AC 1,806 ms
61,704 KB
testcase_25 AC 1,048 ms
62,716 KB
testcase_26 AC 415 ms
61,752 KB
testcase_27 AC 272 ms
60,876 KB
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
import java.nio.*;
public class Main{
    public static void main(String[] args){
        Solve s=new Solve();s.solve();s.exit();
    }
}
class Solve{
    class pos{
        long x,y;
        pos(long x,long y){
            this.x=x;
            this.y=y;
        }   
    }
    public Scanner sc=new Scanner(System.in);
    void exit(){
        sc.close();
    }
    void swap(int[] v,int x,int y){
        v[x]^=v[y];
        v[y]^=v[x];
        v[x]^=v[y];
    }
    public class comp implements Comparator<pos> {
        int _pos(pos v){
            if (v.y < 0) return -1;
            if (v.y == 0 && 0 <= v.x) return 0;
            return 1;
        }
        @Override
        public int compare(pos s,pos t){
            if(s.x==t.x && s.y==t.y)return 0;
            if(_pos(s)!=_pos(t))return _pos(s)<_pos(t)?-1:1;
            else return (0<s.x*t.y-s.y*t.x)?-1:1;
        }
    }
    
    long conv(long x){
        if(x<0)return 1000000007L-(-x)%1000000007L;
        else return x%1000000007L;
    }
    void solve(){
        int n=sc.nextInt();
        long x[],y[];
        x=new long[n];
        y=new long[n];
        for(int i=0;i<n;++i){
            x[i]=sc.nextInt();
            y[i]=sc.nextInt();
        }
        long ans=0;
        for(int i=0;i<n;++i){
            ArrayList<pos>q=new ArrayList<>();
            for(int j=0;j<n;++j){
                if(x[i]==x[j]&&y[i]==y[j])continue;
                q.add(new pos(x[j]-x[i],y[j]-y[i]));
            }
            Collections.sort(q,new comp());
            int l=0,r=0;
            while((int)(l+q.size())!=0&&q.get(0).x*q.get((l+q.size())%q.size()).y-q.get(0).y*q.get((l+q.size())%q.size()).x==0)l--;
            for(int j=0;j<q.size();++j){
                if(j!=0 && q.get(j).x*q.get(j-1).y-q.get(j).y*q.get(j-1).x!=0)l=j-1;
                while(r!=(int)(j+q.size())&&q.get(j).x*q.get(r%q.size()).y-q.get(j).y*q.get(r%q.size()).x>=0)r++;
                ans+=conv(conv(conv(r-l)*conv(x[i]))*conv(y[i]+q.get(j).y));
                ans%=1000000007L;
                ans+=conv(conv(conv(r-l)*conv(-y[i]))*conv(x[i]+q.get(j).x));
                ans%=1000000007L;
            }
        }
        System.out.println(ans);
    }
}
0