結果
| 問題 |
No.180 美しいWhitespace (2)
|
| ユーザー |
 uwi
|
| 提出日時 | 2015-04-06 19:07:54 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,248 bytes |
| コンパイル時間 | 3,864 ms |
| コンパイル使用メモリ | 85,744 KB |
| 実行使用メモリ | 51,384 KB |
| 最終ジャッジ日時 | 2024-07-04 03:27:10 |
| 合計ジャッジ時間 | 7,747 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 4 |
| other | WA * 31 |
ソースコード
package q4xx;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Q425R {
InputStream is;
PrintWriter out;
String INPUT = "400\r\n" +
"15022680 12\r\n" +
"17414387 9\r\n" +
"14365202 12\r\n" +
"8600582 11\r\n" +
"12843553 11\r\n" +
"21438996 7\r\n" +
"18587559 7\r\n" +
"26031859 4\r\n" +
"22034856 9\r\n" +
"12026269 11\r\n" +
"9046254 11\r\n" +
"7354782 15\r\n" +
"30489020 0\r\n" +
"2123621 16\r\n" +
"19343135 9\r\n" +
"20699263 7\r\n" +
"5445555 13\r\n" +
"27288544 5\r\n" +
"30880019 4\r\n" +
"18396204 9\r\n" +
"14248773 13\r\n" +
"25641537 7\r\n" +
"10050252 11\r\n" +
"22482527 6\r\n" +
"26709380 5\r\n" +
"17006576 9\r\n" +
"31827844 1\r\n" +
"20190531 6\r\n" +
"23755985 4\r\n" +
"34402633 0\r\n" +
"4580829 18\r\n" +
"15833712 10\r\n" +
"26538156 5\r\n" +
"24299390 3\r\n" +
"9252529 14\r\n" +
"24275089 4\r\n" +
"15581069 10\r\n" +
"14667196 11\r\n" +
"12716590 10\r\n" +
"10233993 13\r\n" +
"32804667 1\r\n" +
"22323120 5\r\n" +
"15139615 10\r\n" +
"17464112 10\r\n" +
"6201626 17\r\n" +
"33000006 2\r\n" +
"12517963 11\r\n" +
"13475302 10\r\n" +
"18334766 8\r\n" +
"19221282 9\r\n" +
"14437141 12\r\n" +
"10783350 14\r\n" +
"18952923 10\r\n" +
"27843274 3\r\n" +
"16367080 11\r\n" +
"34972773 0\r\n" +
"15544944 12\r\n" +
"35648726 2\r\n" +
"25046629 5\r\n" +
"11330536 11\r\n" +
"7137810 12\r\n" +
"56605 17\r\n" +
"16176917 9\r\n" +
"15712532 10\r\n" +
"25582514 7\r\n" +
"9453854 12\r\n" +
"19438317 9\r\n" +
"1732826 17\r\n" +
"3327744 14\r\n" +
"32413352 1\r\n" +
"32619990 0\r\n" +
"27909997 1\r\n" +
"30606406 3\r\n" +
"2597208 15\r\n" +
"10691143 12\r\n" +
"9479519 14\r\n" +
"10913381 12\r\n" +
"20694839 6\r\n" +
"22198076 9\r\n" +
"11108709 10\r\n" +
"9966645 12\r\n" +
"30624554 4\r\n" +
"21196588 9\r\n" +
"18959779 9\r\n" +
"12795725 13\r\n" +
"29546256 2\r\n" +
"296589 18\r\n" +
"18318465 9\r\n" +
"11479735 11\r\n" +
"31618960 0\r\n" +
"8830760 14\r\n" +
"8115643 13\r\n" +
"11529383 11\r\n" +
"33045590 0\r\n" +
"5747800 13\r\n" +
"12296103 9\r\n" +
"6298198 17\r\n" +
"24010571 8\r\n" +
"8023796 16\r\n" +
"15028425 9\r\n" +
"33864244 2\r\n" +
"19176705 7\r\n" +
"20327961 5\r\n" +
"27840616 6\r\n" +
"994247 16\r\n" +
"3678897 18\r\n" +
"16398231 7\r\n" +
"25543731 3\r\n" +
"16045829 8\r\n" +
"33504508 1\r\n" +
"29415891 2\r\n" +
"27497005 6\r\n" +
"20214287 6\r\n" +
"35449354 0\r\n" +
"24827021 4\r\n" +
"27726432 5\r\n" +
"1065658 17\r\n" +
"25770830 7\r\n" +
"5020363 14\r\n" +
"3128985 18\r\n" +
"19267173 7\r\n" +
"5582531 14\r\n" +
"26383115 5\r\n" +
"7380253 16\r\n" +
"35895405 1\r\n" +
"11717159 10\r\n" +
"24028854 3\r\n" +
"30631848 1\r\n" +
"8312417 11\r\n" +
"30477684 3\r\n" +
"8980694 12\r\n" +
"1003845 19\r\n" +
"4769506 13\r\n" +
"14684653 9\r\n" +
"12497291 10\r\n" +
"3028928 16\r\n" +
"17109081 7\r\n" +
"33810527 0\r\n" +
"26605715 5\r\n" +
"2987295 14\r\n" +
"5783066 14\r\n" +
"10635604 10\r\n" +
"26601517 3\r\n" +
"32760213 2\r\n" +
"28119682 1\r\n" +
"5856259 14\r\n" +
"5474427 15\r\n" +
"2885857 17\r\n" +
"6654906 14\r\n" +
"21399618 9\r\n" +
"34227274 2\r\n" +
"34440599 2\r\n" +
"30006403 2\r\n" +
"23521126 8\r\n" +
"28116728 1\r\n" +
"32230777 3\r\n" +
"23907226 6\r\n" +
"16001292 11\r\n" +
"21644704 7\r\n" +
"30708961 0\r\n" +
"23690877 8\r\n" +
"18190308 7\r\n" +
"3805398 16\r\n" +
"15493730 12\r\n" +
"15408341 12\r\n" +
"7366923 12\r\n" +
"20794272 7\r\n" +
"2021966 17\r\n" +
"18147651 11\r\n" +
"4939822 16\r\n" +
"5175265 13\r\n" +
"37514375 1\r\n" +
"5005233 13\r\n" +
"20964390 5\r\n" +
"3430053 14\r\n" +
"32055238 1\r\n" +
"4158371 15\r\n" +
"18582587 7\r\n" +
"20793734 6\r\n" +
"20243656 6\r\n" +
"37803011 0\r\n" +
"13405815 9\r\n" +
"3150782 18\r\n" +
"12831123 9\r\n" +
"30147964 3\r\n" +
"10523743 11\r\n" +
"13653737 9\r\n" +
"10392566 14\r\n" +
"29681063 5\r\n" +
"24010874 6\r\n" +
"3480364 16\r\n" +
"18576904 8\r\n" +
"20976759 9\r\n" +
"24445146 5\r\n" +
"1785455 19\r\n" +
"4973989 17\r\n" +
"59579 18\r\n" +
"14301494 10\r\n" +
"9674130 11\r\n" +
"26617190 2\r\n" +
"20619615 8\r\n" +
"24262915 6\r\n" +
"12382946 10\r\n" +
"33626189 0\r\n" +
"11915198 13\r\n" +
"12567003 13\r\n" +
"26305244 4\r\n" +
"21333031 7\r\n" +
"29858963 5\r\n" +
"11706288 12\r\n" +
"36338522 1\r\n" +
"12931328 12\r\n" +
"12939350 9\r\n" +
"26790722 5\r\n" +
"5039346 15\r\n" +
"14670527 8\r\n" +
"24295674 4\r\n" +
"19622711 6\r\n" +
"30792270 0\r\n" +
"8692831 12\r\n" +
"13580569 9\r\n" +
"33396565 0\r\n" +
"31966351 4\r\n" +
"36993143 1\r\n" +
"15503507 8\r\n" +
"2247896 17\r\n" +
"34441591 2\r\n" +
"34470184 1\r\n" +
"17974411 9\r\n" +
"9236190 15\r\n" +
"31490343 2\r\n" +
"8983872 13\r\n" +
"2919743 15\r\n" +
"31063566 1\r\n" +
"33035390 0\r\n" +
"31528100 3\r\n" +
"5166097 13\r\n" +
"14552962 11\r\n" +
"4214298 15\r\n" +
"31039165 0\r\n" +
"16738278 8\r\n" +
"27750684 5\r\n" +
"10203014 11\r\n" +
"31620038 2\r\n" +
"10024386 13\r\n" +
"331630 19\r\n" +
"25722720 3\r\n" +
"1650713 19\r\n" +
"39564999 0\r\n" +
"6961866 13\r\n" +
"2739681 14\r\n" +
"38092726 0\r\n" +
"6689854 12\r\n" +
"12418996 14\r\n" +
"15590870 9\r\n" +
"36717380 0\r\n" +
"1030779 18\r\n" +
"36388536 0\r\n" +
"29978374 5\r\n" +
"9104604 12\r\n" +
"25630868 7\r\n" +
"16152158 11\r\n" +
"201321 17\r\n" +
"23907663 6\r\n" +
"35071025 2\r\n" +
"9039854 11\r\n" +
"33419498 2\r\n" +
"23538640 5\r\n" +
"31786324 3\r\n" +
"30733974 3\r\n" +
"39323892 0\r\n" +
"4620058 15\r\n" +
"15093790 10\r\n" +
"6520501 13\r\n" +
"15192042 8\r\n" +
"3667950 15\r\n" +
"36144641 0\r\n" +
"34489634 1\r\n" +
"26652813 2\r\n" +
"11891713 10\r\n" +
"10739780 10\r\n" +
"28063945 6\r\n" +
"16686502 10\r\n" +
"18215338 7\r\n" +
"12469890 11\r\n" +
"29485805 2\r\n" +
"10735310 10\r\n" +
"29360958 5\r\n" +
"12027717 14\r\n" +
"748036 16\r\n" +
"22048382 8\r\n" +
"12164046 13\r\n" +
"30157418 4\r\n" +
"24196719 7\r\n" +
"18688403 10\r\n" +
"6926474 16\r\n" +
"4880651 13\r\n" +
"17220987 8\r\n" +
"2172869 16\r\n" +
"13998482 11\r\n" +
"10855490 11\r\n" +
"30332709 0\r\n" +
"33283150 0\r\n" +
"5211405 16\r\n" +
"38924927 0\r\n" +
"3720465 15\r\n" +
"5197220 16\r\n" +
"979220 16\r\n" +
"24013751 4\r\n" +
"10259372 14\r\n" +
"2945851 17\r\n" +
"4447718 16\r\n" +
"10481100 11\r\n" +
"11684856 10\r\n" +
"3724519 14\r\n" +
"31332748 2\r\n" +
"23470085 7\r\n" +
"5746861 14\r\n" +
"14459885 12\r\n" +
"3285834 18\r\n" +
"6983769 15\r\n" +
"35170057 2\r\n" +
"26347197 5\r\n" +
"21064262 6\r\n" +
"22881825 8\r\n" +
"3104960 16\r\n" +
"9036278 15\r\n" +
"31150701 3\r\n" +
"28427868 1\r\n" +
"4864977 16\r\n" +
"20016967 8\r\n" +
"23627746 4\r\n" +
"13291362 11\r\n" +
"28795438 2\r\n" +
"27072122 6\r\n" +
"3525815 15\r\n" +
"33469958 0\r\n" +
"24481159 7\r\n" +
"30641845 0\r\n" +
"17705339 9\r\n" +
"5441092 15\r\n" +
"19253697 6\r\n" +
"465024 19\r\n" +
"26781910 4\r\n" +
"36303396 0\r\n" +
"13371854 9\r\n" +
"24729974 3\r\n" +
"22840301 6\r\n" +
"33758520 1\r\n" +
"5277117 13\r\n" +
"21217548 5\r\n" +
"30649878 4\r\n" +
"21394595 5\r\n" +
"11093443 11\r\n" +
"3406768 17\r\n" +
"12389241 11\r\n" +
"26516894 4\r\n" +
"19823372 6\r\n" +
"876618 16\r\n" +
"33186505 0\r\n" +
"28334001 5\r\n" +
"3488670 15\r\n" +
"28604736 3\r\n" +
"27955650 3\r\n" +
"3285697 15\r\n" +
"33890854 2\r\n" +
"16935007 8\r\n" +
"7496559 15\r\n" +
"33246441 1\r\n" +
"29492234 5\r\n" +
"21375358 8\r\n" +
"14827908 11\r\n" +
"29474276 2\r\n" +
"12920341 11\r\n" +
"39126790 0\r\n" +
"7064843 13\r\n" +
"17782485 8\r\n" +
"32840639 2\r\n" +
"19739450 7\r\n" +
"6003479 13\r\n" +
"29071030 5\r\n" +
"4609440 14\r\n" +
"15307151 8\r\n" +
"9454147 13\r\n" +
"33766144 3\r\n" +
"1154834 15\r\n" +
"9783320 11\r\n" +
"27167436 4\r\n" +
"3851566 18\r\n" +
"15790342 8\r\n" +
"4874563 15\r\n" +
"18917065 8\r\n" +
"1263463 17\r\n" +
"4101388 18\r\n" +
"23815712 6\r\n" +
"17989892 8\r\n" +
"8641586 12\r\n" +
"653210 15\r\n" +
"20220011 8\r\n" +
"22408618 7\r\n" +
"";
void solve()
{
int n = ni();
int[][] co = new int[n][];
for(int i = 0;i < n;i++){
co[i] = na(2);
}
long x = goldenSectionMethod(1, 10000000000L, co);
long v = f(x, co);
if(v > f(x+1, co)){
x++;
v = f(x+1, co);
}
if(v > f(x+2, co)){
x++;
v = f(x+2, co);
}
out.println(x);
}
public static long goldenSectionMethod(long low, long high, int[][] co)
{
final double tau = (Math.sqrt(5)-1)/2;
long nl = Math.round(high + tau * (low - high));
long nh = Math.round(low + tau * (high - low));
long vl = f(nl, co);
long vh = f(nh, co);
while(high - low > 2){
// tr(low, nl, nh, high);
// tr(f(low, co), f(nl, co), f(nh, co), f(high, co));
// tr();
if(vl <= vh){
high = nh;
vh = vl;
nh = nl;
nl = Math.round(high + tau * (low - high));
if(nl == nh)nl--;
vl = f(nl, co);
}else{
low = nl;
vl = vh;
nl = nh;
nh = Math.round(low + tau * (high - low));
if(nh == nl)nh++;
vh = f(nh, co);
}
}
return low;
}
public static long f(long x, int[][] co)
{
long max = 0, min = Long.MAX_VALUE;
for(int[] c : co){
long v = c[0] + c[1] * x;
if(v > max)max = v;
if(v < min)min = v;
}
return max-min;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new Q425R().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}