P1

实际上只需要统计不同斜率的个数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
bool o;
ll A, B;
ll C[320];
ll J[320];
bool cmp(int x, int y) {
    if (A * C[x] + B * J[x] != A * C[y] + B * J[y]) {
        return A * C[x] + B * J[x] < A * C[y] + B * J[y];
    }
    if (o) {
        return C[x] < C[y];
    } else {
        return C[x] > C[y];
    }
}
ll gcd(ll x, ll y) {
    return y ? gcd(y, x % y) : x;
}
int main() {
    int t;
    scanf("%d", &t);
    for (int tt = 1; tt <= t; tt++) {
        scanf("%d", &n);
        vector<vector<int> > z;
        vector<int> r;
        for (int i = 0; i < n; i++) {
            scanf("%lld%lld", &C[i], &J[i]);
            r.push_back(i);
        }
        set<pair<int, int> > fuck;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && C[i] > C[j]) {
                    if (J[i] < J[j]) {
                        B = C[i] - C[j];
                        A = J[j] - J[i];
                        ll g = gcd(A, B);
                        A /= g;
                        B /= g;
                        fuck.insert(make_pair(A, B));
                    }
                }
            }
        }
        printf("Case #%d: %d\n", tt, (int)fuck.size() + 1);
    }
    return 0;
}

P2

看起来就是乱搞
并不需要利用可以模仿别人这一点

P3

经典论文题

from fractions import *
# C / J
t = input()
def gao(ax, ay, bx, by):
    if by == 0 or ax / ay < (bx - 1) / by:
        return ax / ay + 1, 1
    else:
        xx, yy = gao(by, bx - ax / ay * by, ay, ax % ay)
        return yy + ax / ay * xx, xx

for tt in range(1, t + 1):
    n = input()
    a = []
    A = Fraction(1, 10 ** 9 + 1)
    B = Fraction(10 ** 9 + 1, 1)
    for i in range(n):
        x, y = map(int, raw_input().split())
        a.append((x, y))
    for i in range(1, n):
        if a[i - 1][0] >= a[i][0] and a[i - 1][1] >= a[i][1]:
            A = B
            break
        elif a[i - 1][0] <= a[i][0] and a[i - 1][1] <= a[i][1]:
            continue
        elif a[i - 1][0] > a[i][0] and a[i - 1][1] < a[i][1]:
            A = max(A, Fraction(a[i - 1][0] - a[i][0], a[i][1] - a[i - 1][1]))
        elif a[i - 1][1] > a[i][1] and a[i - 1][0] < a[i][0]:
            B = min(B, Fraction(a[i][0] - a[i - 1][0], a[i - 1][1] - a[i][1]))
#  print A, B
    if A < B:
        X, Y = gao(A.numerator, A.denominator, B.numerator, B.denominator)
        print 'Case #%d: %d %d' % (tt, Y, X)
    else:
        print 'Case #%d: IMPOSSIBLE' % (tt)

P4

没看