# Baidu Astar 2012 初賽

Day 1

### 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

### 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;

}
}
```