結果

問題 No.461 三角形はいくつ？
ユーザー 37zigen37zigen
提出日時 2016-12-16 02:35:22
言語 Java21
(openjdk 21)
結果
AC  
実行時間 734 ms / 5,000 ms
コード長 1,945 bytes
コンパイル時間 5,748 ms
コンパイル使用メモリ 78,116 KB
実行使用メモリ 62,944 KB
最終ジャッジ日時 2023-08-20 08:46:16
合計ジャッジ時間 28,189 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
55,832 KB
testcase_01 AC 127 ms
55,880 KB
testcase_02 AC 126 ms
55,728 KB
testcase_03 AC 126 ms
55,452 KB
testcase_04 AC 193 ms
56,960 KB
testcase_05 AC 734 ms
61,168 KB
testcase_06 AC 531 ms
61,516 KB
testcase_07 AC 638 ms
61,188 KB
testcase_08 AC 447 ms
61,172 KB
testcase_09 AC 161 ms
56,512 KB
testcase_10 AC 341 ms
60,592 KB
testcase_11 AC 492 ms
61,420 KB
testcase_12 AC 424 ms
61,064 KB
testcase_13 AC 533 ms
61,780 KB
testcase_14 AC 533 ms
60,936 KB
testcase_15 AC 533 ms
61,284 KB
testcase_16 AC 431 ms
60,996 KB
testcase_17 AC 438 ms
61,388 KB
testcase_18 AC 572 ms
61,560 KB
testcase_19 AC 543 ms
59,668 KB
testcase_20 AC 625 ms
61,836 KB
testcase_21 AC 539 ms
61,116 KB
testcase_22 AC 651 ms
61,180 KB
testcase_23 AC 502 ms
61,116 KB
testcase_24 AC 475 ms
62,944 KB
testcase_25 AC 451 ms
60,088 KB
testcase_26 AC 476 ms
60,264 KB
testcase_27 AC 278 ms
60,368 KB
testcase_28 AC 497 ms
61,548 KB
testcase_29 AC 517 ms
61,324 KB
testcase_30 AC 512 ms
60,928 KB
testcase_31 AC 521 ms
61,616 KB
testcase_32 AC 640 ms
62,336 KB
testcase_33 AC 271 ms
60,256 KB
testcase_34 AC 287 ms
60,520 KB
testcase_35 AC 295 ms
60,192 KB
testcase_36 AC 470 ms
61,160 KB
testcase_37 AC 475 ms
61,644 KB
testcase_38 AC 444 ms
61,036 KB
testcase_39 AC 453 ms
61,000 KB
testcase_40 AC 481 ms
60,808 KB
testcase_41 AC 486 ms
60,920 KB
testcase_42 AC 529 ms
61,228 KB
testcase_43 AC 522 ms
60,812 KB
testcase_44 AC 533 ms
61,720 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.concurrent.SynchronousQueue;

public class Q461 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<Fraction>[] f = new ArrayList[3];
		for (int i = 0; i < 3; ++i) {
			f[i] = new ArrayList<>();
			f[i].add(new Fraction(1, 1));
		}
		for (int i = 0; i < n; ++i) {
			int p = sc.nextInt();
			long a = sc.nextLong();
			long b = sc.nextLong();
			f[p].add(new Fraction(a, a + b));
		}
		Collections.sort(f[1]);
		Collections.sort(f[2]);
		long ans = 0;
		for (Fraction f0 : f[0]) {
			int i1 = f[2].size() - 1;
			int i2 = f[2].size() - 1;
			int i3 = f[2].size() - 1;
			for (Fraction f1 : f[1]) {
				if (f0.add(f1).compareTo(ONE) == -1)
					continue;
				while (i1 > 0 && f0.add(f1).add(f[2].get(i1)).compareTo(TWO) > 0)
					--i1;
				while (i2 >= 0 && f1.add(f[2].get(i2)).compareTo(ONE) != -1)
					--i2;
				while (i3 >= 0 && f0.add(f[2].get(i3)).compareTo(ONE) != -1)
					--i3;
				if (f0.add(f1).add(f[2].get(i1)).compareTo(TWO) == 0)
					--ans;
				ans += (f[2].size() - 1) - Math.max(i3, i2);
			}
		}
		System.out.println(ans);
	}

	static Fraction ONE = new Fraction(1, 1);
	static Fraction TWO = new Fraction(2, 1);

	static class Fraction implements Comparable<Fraction> {
		long x;
		long y;

		public Fraction(long x, long y) {
			this.x = x;
			this.y = y;
		}

		Fraction add(Fraction o) {
			return new Fraction(x * o.y + o.x * y, y * o.y);
		}

		Fraction subtruct(Fraction o) {
			return new Fraction(x * o.y - o.x * y, y * o.y);
		}

		Fraction mul(Fraction o) {
			return new Fraction(x * o.x, y * o.y);
		}

		boolean equiv(Fraction o) {
			return x * o.y == y * o.x;
		}

		@Override
		public int compareTo(Fraction o) {
			if (o.y < 0 || y < 0)
				throw new AssertionError();
			return Long.compare(x * o.y, o.x * y);
		}
	}
}
0