run.java

第四届百度杯编程大赛final解题报告+标程

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);
	    }
	}
}