?? run.java
字號:
import java.io.*;
import java.util.*;
public class run {
static final int maxn = 100010;
static Scanner cin;
static final double eps = 1e-9;
static final int sgn(final double x) {
return (x > eps ? 1 : 0) - (x < eps ? 1 : 0);
}
static class line implements Comparable {
double a, b;
line(final double _a, final double _b) {a = _a; b = _b;}
public int compareTo(Object obj) {
if (obj instanceof line) {
line b = (line) obj;
if (this.a < b.a)
return -1;
else if (this.a > b.a)
return 1;
}
return 0;
}
boolean less(final line b){
return a < b.a;
}
};
static final boolean inter(final line l1, final line l2, double inter_x[]) {
if (sgn(l1.a - l2.a) == 0)
return false;
inter_x[0] = (l2.b - l1.b) / (l1.a - l2.a);
return true;
}
static int n;
static line l[];
static double x[] = new double[maxn];
static int id[] = new int[maxn];
static int top;
public static void main(String args[]) throws Exception {
cin = new Scanner(System.in);
int ca = cin.nextInt();
for (int c = 0; c < ca; c++) {
n = cin.nextInt();
l = new line[n];
for (int i = 0; i < n; i++) {
int t1 = cin.nextInt();
int t2 = cin.nextInt();
l[i] = new line(t1, t2);
}
Arrays.sort(l);
top = 2;
x[0] = 0;
x[1] = 1e10;
id[0] = 0;
id[1] = -1;
for (int i = 1; i < n; i++) {
for (int j = top - 1; j > 0; j--) {
double inter_x[] = new double[1];
if (inter(l[i], l[id[j - 1]], inter_x)) {
if (inter_x[0] > x[j - 1] && inter_x[0] < x[j] + eps) {
x[j] = inter_x[0];
id[j] = i;
x[j + 1] = 1e10;
id[j + 1] = -1;
top = j + 2;
break;
}
}
if (j == 1 && inter_x[0] < eps) {
x[0] = 0;
id[0] = i;
x[1] = 1e10;
id[1] = -1;
top = 2;
}
}
}
System.out.printf("%d\n", top - 1);
}
}
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -