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
没看