Day 1
Brief description:
…
Analysis:
…
const int N = 100009;
pair<LL, LL> a[N], b[N];
#define x first
#define y second
LL f(int u, int v){
return a[u].y-a[v].x <= 0 ? 0 : (a[v].y-a[u].x)*(a[u].y-a[v].x);
}
bool cmp(const pair<LL, LL>& a, const pair<LL, LL>& b){
return a.x<b.x || a.x==b.x && a.y>b.y ;
}
int main(){
int n; while (cin>>n){
REP(i, n)
scanf("%lld %lld", &b[i].x, &b[i].y);
LL res=0; int m=0; sort(b, b+n, cmp); for (int i=0,j;i<n;i=j){
j=i+1; while (j<n && b[j].y<b[i].y){
checkMax(res, (b[j].y-b[j].x)*(b[i].y-b[i].x));
j++;
}
a[m++]=b[i];
}
n = m; int j = 1; checkMax(res,f(0,1)); FOR(i, 2, n){
checkMax(res, f(j++,i) );
while (j<i && f(j,i) >res)
res=f(j++, i);
}
cout<<res<<endl;
}
}
const int N = 109, M = 10;
bool dp[N+1][M+1][M+1][1<<M]; LL bonus[1<<M];
int a[M], b[M], c[M];
int n, m, p;
VI L, Lb;
bool G[M][M*M];
LL f(int s){
LL ans = 0;
REP(i, m) if (_1(s, i)){
ans += b[i];
}
REP(i, SZ(L)) if ((s&L[i]) == L[i]){
ans += Lb[i];
}
return ans;
}
int main() {
/*
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
*/
Rush{
RD(n, m, p); REP(i, m) RD(a[i]); REP(i, m) RD(c[i]); REP(i, m) RD(b[i]);
int x, y; CLR(L, Lb); REP(i, p){
RD(x, y); int s = 0;REP(j, x) s |= _1(RD()-1);
// cout << s << endl;
L.PB(s); Lb.PB(y);
}
RST(G); REP(i, m){
if (a[i] == 0) continue;
if (a[i] == 1){
REP(j, m) if (RD() == 1) G[i][j] = true;
}
else {
REP_2(j, k, m, m) if (RD() == 1) G[i][j*m+k] = true;
}
}
REP_C(s, _1(m)) bonus[s] = f(s);
FLC(dp, false); dp[0][m][m][0] = true;
LL ans = 0;
FOR_1(i, 0, n) REP(l1, m+1) REP(l2, m+1) REP_C(s, _1(m)){
if (!dp[i][l1][l2][s]) continue;
//cout << i << " " << s << endl;
if (i == n) checkMax(ans, bonus[s]);
REP(k, m) if (i + c[k] <= n){
if (!a[k] || a[k] == 1 && l2 != m && G[k][l2] || a[k] == 2 && l1 != m && l2 != m && G[k][l1*m+l2]){
dp[i+c[k]][l2][k][s|_1(k)] = true;
}
}
}
/*
REP_C(i, _1(m)){
cout << i << " " << f(i) << endl;
}
*/
cout << ans << endl;
}
}
/*
1110
// 101
*/
Day 2
Brief description:
…
Analysis:
…
const int N = 1009;
int x[N], y[N], a[N], b[N], W[N];
DB vx[N], vy[N];
int n;
VD L;
int main(){
/*
#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif
*/
while (scanf("%d", &n) != EOF && n){
REP(i, n){
RD(x[i], y[i], a[i], b[i]);
vx[i] = DB (a[i] - x[i]) / 10;
vy[i] = DB (b[i] - y[i]) / 10;
}
if (n <= 2){
cout << n << endl;
continue;
}
CLR(L);
L.PB(0), L.PB(10);
REP(i, n) FOR(j, i+1, n) FOR(k, j+1, n){
// Po v1 = PO( (x[j] + vx[j] * t) - (x[i] + vx[i] * t), (y[j] + vy[j] * t) - (y[i] + vy[i] * t) );
// Po v2 = PO( (x[k] + vx[k] * t) - (x[i] + vx[i] * t), (y[k] + vy[k] * t) - (y[i] + vy[i] * t) );
//(x[j] - x[i]) + t (vx[j] - vx[i]) (y[k] - y[i]) + t (vy[k] - vy[i])
// =
//(x[k] - x[i]) + t (vx[k] - vx[i]) (y[j] - y[i]) + t (vy[j] - vy[i])
DB c = (x[j] - x[i]) * (y[k] - y[i]) - (x[k] - x[i]) * (y[j] - y[i]);
DB b = (vx[j] - vx[i]) * (y[k] - y[i]) + (vy[k] - vy[i]) * (x[j] - x[i])
- ((vx[k] - vx[i]) * (y[j] - y[i]) + (vy[j] - vy[i]) * (x[k] - x[i]));
DB a = (vx[j] - vx[i]) * (vy[k] - vy[i]) - (vx[k] - vx[i]) * (vy[j] - vy[i]);
if (!sgn(a)){
if (sgn(b)){
DB t1 = (-c / b);
if (sgn(t1) >= 0 || sgn(t1, 10) <= 0){
L.PB(t1);
}
}
continue;
}
DB delta = sqr(b) - 4 * a * c;
// cout << i << " " << j << " " << k << " " << delta << endl;
if (sgn(delta) < 0) continue;
if (!sgn(delta)){
DB t = -b / (2*a);
// cout << t << endl;
if (sgn(t) < 0 || sgn(t, 10) > 0) continue;
Po v1 = Po( (x[j] + vx[j] * t) - (x[i] + vx[i] * t), (y[j] + vy[j] * t) - (y[i] + vy[i] * t) );
Po v2 = Po( (x[k] + vx[k] * t) - (x[i] + vx[i] * t), (y[k] + vy[k] * t) - (y[i] + vy[i] * t) );
/*
if (sgn(det(v1, v2))){
cout << "Error" << endl;
}
*/
}
else {
DB t1 = (-b + sqrt(delta)) / (2*a);
if (sgn(t1) >= 0 || sgn(t1, 10) <= 0){
L.PB(t1);
}
t1 = (-b - sqrt(delta)) / (2*a);
if (sgn(t1) >= 0 || sgn(t1, 10) <= 0){
L.PB(t1);
}
}
}
SRT(L);
L.resize(unique(ALL(L)) - L.begin());
int ans = 2;
// cout << n << endl;
REP(ii, SZ(L)){
DB t = L[ii];
vector<Po> pp; CLR(pp);
REP(i, n){
pp.PB( Po( (x[i] + vx[i] * t), (y[i] + vy[i] * t) ));
}
SRT(pp);
vector<Po> ppp = pp;
RST(W);
pp.resize( unique( ALL(pp) ) - pp.begin() );
int nn = SZ(pp);
REP(i, nn){
REP(j, n) if ( pp[i] == ppp[j] ) ++ W[i];
}
REP(i, nn) FOR(j, i+1, nn){
Po v1 = pp[j] - pp[i];
int cnt = W[i] + W[j];
FOR(k, j+1, nn){
Po v2 = pp[k] - pp[i];
if (!sgn(det(v1, v2))){
cnt += W[k];
}
}
checkMax(ans, cnt);
}
}
cout << ans << endl;
}
}
