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;

    }
}

Posted by xiaodao
Category: Astar
Tags: 施工中