顯示具有 TIOJ 標籤的文章。 顯示所有文章
顯示具有 TIOJ 標籤的文章。 顯示所有文章

2015年7月20日 星期一

TIOJ 1501 . Dead at the end of sixth sense

枚舉最小值

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long int int64;

const int64 inf = 10000000000LL;

int64 iabs(int64 a){return max(a, -a);}

int main(){
    int T; scanf("%d", &T);
    while(T--){
        int n; scanf("%d", &n);
        int64 arr[1001];
        for(int lx = 0;lx < n;lx++) scanf("%lld", arr+lx);
        int64 ans = inf;
        for(int lx = 0;lx < n;lx++){
            int64 tab[1001];
            for(int ly = 0;ly < n;ly++) tab[ly] = inf;
            tab[n-1] = arr[n-1], tab[n] = arr[n-1];
            arr[n] = arr[n-1];
            for(int ly = n-2;ly>=0;ly--){
                if(arr[ly] < arr[lx]) continue;
                int64 mm = inf;
                if(arr[ly+1] >= arr[lx]) mm = min(mm, tab[ly+1]);
                if(arr[ly+2] >= arr[lx]) mm = min(mm, tab[ly+2]);
                tab[ly] = max(arr[ly], mm);
            }
            int64 cal = tab[0]-arr[lx];
//            printf("%d -> cal = %lld\n", lx, cal);
            ans = min(tab[0]-arr[lx], ans);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

2015年7月11日 星期六

1111 . [入門] Crucio


#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

char tab[510][510];

int main(){
    int n;
    for(;;){
        scanf("%d", &n);
        if(!n) break;
        for(int lx = 0; lx < n;lx++)
            scanf("%s", tab[lx]);
       
        int dx[4] = {1, 1, 1, 0};
        int dy[4] = {-1, 0, 1, 1};

        int pts[3] = {0};
        for(int lx = 0;lx < n;lx++){
            for(int ly = 0;ly < n;ly++){
                char ch = tab[lx][ly];
                if(ch == '.') continue;
                for(int ld = 0;ld < 4;ld++){
                    bool ok = true;
                    for(int len = -1;len <= 5 and ok;len++){
                        int nx = lx+len*dx[ld], ny = ly+len*dy[ld];
                        bool fg = true;
                        if(nx < 0 or nx >= n or ny < 0 or ny >= n or tab[nx][ny] != ch){
                            fg = false;
                        }
                        ok = fg^(len == -1 or len == 5);

                    }
                    if(ok)
                        pts[ch-'A']++;
                }
            }
        }

        printf("A %d\nB %d\nC %d\n\n", pts[0], pts[1], pts[2]);

    }
    return 0;
}

TIOJ 1108 . 樹的三兄弟



#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

char pre[100], in[100];

void print_tree(int pre1, int pre2, int in1, int in2){
    if(pre1 == pre2) return;
    
    int ptr = in1;
    for(;ptr < in2;ptr++)
        if(in[ptr] == pre[pre1])
            break;

    print_tree(pre1+1, pre1+(ptr-in1)+1, in1, ptr);
    print_tree(pre1+(ptr-in1)+1, pre2, ptr+1, in2);
    printf("%c", pre[pre1]);
    return;
}

int main(){
    while(scanf("%s %s", pre, in) != EOF){
        print_tree(0, strlen(pre), 0, strlen(in)) ;
        puts("");
    }
    return 0;
}   

2015年6月18日 星期四

TIOJ 1224 . 矩形覆蓋面積計算

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long int int64;

struct bst{ // 0-base
    vector<int> ncnt;
    vector<int> cnt;
    vector<int> col;
    int base;
    bst(int n){
        base = (1<<(int)(ceil(log2(n+2))))-1;
        ncnt = vector<int>(2*base+2, 0);
        cnt = vector<int>(2*base+2, 0);
        col = vector<int>(2*base+2, 0);
        for(int lx = 0;lx < n;lx++) cnt[base+lx+2] = 1;
        for(int lx = base;lx;lx--) cnt[lx] = cnt[lx<<1] + cnt[(lx<<1)^1];
        return;
    }

    void modify(int a, int b, int v){
        int nodes[30]; int nc = 0;
        for(a+=base+1, b+=base+3; a^b^1;a>>=1, b>>=1){
            if(~a&1) nodes[nc++] = a^1;
            if(b&1) nodes[nc++] = b^1;
        }
        for(int lx = 0;lx < nc;lx++){
            int nd = nodes[lx];
            //printf("%d -> %d\n", nd, v);
            ncnt[nd] += v;
            if(ncnt[nd] == 0){
                // 1->0
                int det = cnt[nd]-col[nd];
                for(int prc = nd>>1;prc;prc>>=1){
                    col[prc] -= det;
                    if(ncnt[prc]) break;
                }
            }else if(ncnt[nd] == 1 and v == 1){
                // 0->1
                int det = cnt[nd]-col[nd];
                for(int prc = nd>>1;prc;prc>>=1){
                    col[prc] += det;
                    if(ncnt[prc]) break;
                }
            }
        }
        return;
    }

    int query()const{
        return col[1];
    }
};

struct qry{int l, r, v, x; qry(int _l = 0, int _r = 0, int _v = 0, int _x = 0):l(_l),r(_r),v(_v),x(_x){return;}}qrys[200000];
bool operator<(const qry& a, const qry& b){return a.x < b.x;}

int main(){
    int n; scanf("%d", &n);
    for(int lx = 0;lx < n;lx++){
        int l, r, d, u; scanf("%d %d %d %d", &l, &r, &d, &u);
        qrys[lx<<1] = qry(d,u-1,1,l);
        qrys[(lx<<1)^1] = qry(d,u-1,-1,r);
    }
    sort(qrys, qrys+2*n);
    int64 ans = 0;
    int org = 0;
    bst BST(1000000);
    for(int lx = 0;lx < 2*n;lx++){
        //printf("%d %d %d %d\n", qrys[lx].x, qrys[lx].l, qrys[lx].r, qrys[lx].v);
        ans += ((int64)BST.query())*((int64)(qrys[lx].x-org));
        //printf("%lld\n", ans);
        org = qrys[lx].x;
        BST.modify(qrys[lx].l, qrys[lx].r, qrys[lx].v);
    }
    printf("%lld\n", ans);
    return 0;
}

2015年6月5日 星期五

TIOJ 1106 . 遇見一株樹


#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct node{
    int nc, h;
    node(int _h = 0){nc = 0;h = _h;return;}
}stk[1000000];

int ptr;

char buf[1000000];

int main(){
    while(scanf("%s", buf) != EOF){
        ptr = 1;
        stk[0] = node(1);
        int max_nc = 0;
        int max_h = 1;
        int leaf_cnt = 0;
        for(int lx = 0;buf[lx] != 0;lx++){
            if(buf[lx] == '('){
                stk[ptr-1].nc++;
                stk[ptr] = node(stk[ptr-1].h+1);
                ptr++;
            }else if(buf[lx] == ')'){
                max_h = max(max_h, stk[ptr-1].h);
                max_nc = max(max_nc, stk[ptr-1].nc);
                ptr--;
            }else if(buf[lx] == '*'){
                stk[ptr-1].nc++;
                leaf_cnt++;
            }
        }

        printf("%d %d %d\n", leaf_cnt, max_h, max_nc);
    }
    return 0;
}

2015年6月3日 星期三

TIOJ 1085 . 三維迷宮問題



#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

int gx(int a){return (a%50) + 1;}
int gy(int a){return ((a/50)%50) + 1;}
int gz(int a){return ((a/2500)%50) + 1;}
int tv(int x, int y, int z){return (x-1) + (y-1)*50 + (z-1)*2500;}

int tab[52][52][52] = {0};
int vis[52][52][52];

int main(){
    int xx, yy, zz; scanf("%d %d %d", &xx, &yy, &zz);
    memset(vis, -1, sizeof(vis));

    for(int lx = 1;lx <= xx;lx++) for(int ly = 1;ly <= yy;ly++) tab[lx][ly][0] = tab[lx][ly][zz+1] = 1;
    for(int lx = 1;lx <= xx;lx++) for(int lz = 1;lz <= zz;lz++) tab[lx][0][lz] = tab[lx][yy+1][lz] = 1;
    for(int lz = 1;lz <= zz;lz++) for(int ly = 1;ly <= yy;ly++) tab[0][ly][lz] = tab[xx+1][ly][lz] = 1;
   
    for(int lz = 1;lz <= zz;lz++)
        for(int ly = 1;ly <= yy;ly++)
            for(int lx = 1;lx <= xx;lx++)
                scanf("%d", &tab[lx][ly][lz]);
   
    if(tab[1][1][1]){
        puts("no route");
        return 0;
    }
   
    vis[1][1][1] = 0;
    queue<int> que;
    que.push(0);
   
    const int dx[] = {0, 0, 0, 0, 1, -1},
              dy[] = {1, -1, 0, 0, 0, 0},
              dz[] = {0, 0, 1, -1, 0, 0};
   
    while(que.size()){
        int prc = que.front(); que.pop();
        int px = gx(prc), py = gy(prc), pz = gz(prc);
        for(int t = 0;t < 6;t++){
            int nx = px + dx[t], ny = py + dy[t], nz = pz + dz[t];
            if(tab[nx][ny][nz]) continue;
            if(vis[nx][ny][nz]!=-1) continue;
            vis[nx][ny][nz] = prc;
            que.push(tv(nx, ny, nz));
        }
    }
   
    if(vis[xx][yy][zz] == -1){
        puts("no route");
        return 0;
    }
   
    vector<int> hist;
    int now = tv(xx, yy, zz);
    while(now){
        hist.push_back(now);
        now = vis[gx(now)][gy(now)][gz(now)];
    }
   
    printf("(1,1,1)");
    for(int lx = ((int)hist.size())-1;lx>=0;lx--){
        int prc = hist[lx];
        printf("->(%d,%d,%d)",gx(prc),gy(prc),gz(prc));
    }
    puts("");
    return 0;
}

TIOJ 1084 . 一筆畫問題

dfs倒著吐回去


#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int tab[500][500];
int vcnt[500];
int stk[1025], stkcnt;

void dfs(int a){
    bool flag = false;
    for(int lx = 0;lx < 500;lx++){
        if(tab[a][lx]){
            tab[a][lx]--;
            tab[lx][a]--;
            dfs(lx);
            flag = true;
            stk[stkcnt++] = a+1;
        }
    }
    if(!flag) stk[stkcnt++] = a+1;
    return;
}

int main(){
    int c;
    while(scanf("%d", &c)&&c){
        memset(tab, 0, sizeof(tab));
        memset(vcnt, 0, sizeof(vcnt));
        stkcnt = 0;

        while(c--){
            int a, b; scanf("%d %d", &a, &b); a--, b--;
            tab[a][b]++, tab[b][a]++;
            vcnt[a]++, vcnt[b]++;
        }
        bool check = true;
        for(int lx = 0;lx < 500 and check;lx++)
            check = not (vcnt[lx]&1);
       
        int sm = -1;
        if(check) while(!vcnt[++sm]);
        else  while(!(vcnt[++sm]&1));
        dfs(sm);

        for(int lx = stkcnt-1;lx>=0;lx--)
            if(lx == stkcnt-1 or stk[lx] != stk[lx+1])
                printf("%d\n", stk[lx]);
        puts("");
    }
    return 0;
}

2015年5月21日 星期四

TIOJ 1798 . Can You Arrive?

LCA + DisjointSet

一個樹上路徑們並查的故事。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;

class bst{
public:
    bst(int n, int* _val){
        base = (1<<(int)(ceil(log2(n+3))))-1;
        tree = new int[base*2+2];
        val = new int[base+2];
        for(int lx = 0;lx < base+1;lx++) val[lx] = 10000000, tree[base+lx+1]=lx;
        for(int lx = 0;lx < n;lx++) val[lx+1] = _val[lx];
        for(int lx = base;lx;lx--){
            if(val[tree[lx*2]] > val[tree[lx*2+1]])
                tree[lx]= tree[lx*2+1];
            else
                tree[lx] = tree[lx*2];
        }
        return;
    }
    int query(int a, int b){
        a++, b++;
        int ret = tree[base+a+1];
        for(a+=base, b+=base+2;a^b^1;a>>=1, b>>=1){
            if(~a&1) if(val[ret] > val[tree[a^1]]) ret = tree[a^1];
            if(b&1) if(val[ret] > val[tree[b^1]]) ret = tree[b^1];
        }
        return ret-1;
    }
private:
    int base;
    int* tree;
    int* val;
};

VVI graph;
int ptr;
int hei[1000000];
int arr[2000000];
int harr[2000000];
int ac1[1000000];
int ato[1000000][2];
bst* lca_bst;

void dfs(int fa, int nd){
    //printf("visit at %d\n", nd+1);
    ac1[nd] = fa, hei[nd] = hei[fa]+1;
    ato[nd][0] = ptr; arr[ptr] = nd; harr[ptr++] = hei[nd];
    for(int lx = 0;lx < graph[nd].size();lx++){
        if(graph[nd][lx] == fa) continue;
        dfs(nd, graph[nd][lx]);
        ato[nd][1] = ptr; arr[ptr] = nd; harr[ptr++] = hei[nd];
    }
    ato[nd][1] = ptr; arr[ptr] = nd; harr[ptr++] = hei[nd];
    return;
}

void build(int n){
    ptr = 0, hei[0] = 0; dfs(0, 0);
   
    /*for(int lx = 0;lx < ptr;lx++)
        printf("%02d ", arr[lx]+1);
    puts("");

    for(int lx = 0;lx < ptr;lx++)
        printf("%02d ", harr[lx]);
    puts("");*/
   
    lca_bst = new bst(ptr, harr);
    return;
}

int lca(int a, int b){
    int ll = min(ato[a][0], ato[b][0]), rr = max(ato[a][1], ato[b][1]);
    //printf("qlca(%d %d)\n", ll, rr);
    return arr[lca_bst->query(ll, rr)];
}

struct path{ int h, x, y; }paths[2000000];
bool operator<(path a, path b){return a.h<b.h;}

int fat[1000000];
int qfat(int a){return fat[a]==a ? a: fat[a]=qfat(fat[a]);}
void join(int a, int b){fat[qfat(a)] = qfat(b); return;}

int main(){
    int n, m, k, q;
    scanf("%d %d %d %d", &n, &m, &k, &q);
    graph = VVI(n, VI());
    for(int lx = 0;lx < m;lx++){
        int a, b; scanf("%d %d", &a, &b); a--, b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
        //printf("%d <-> %d\n", a+1, b+1);
    }

    build(n);
   
    for(int lx = 0;lx < k;lx++){
        int a, b; scanf("%d %d", &a, &b); a--, b--;
        int c = lca(a, b);
        //printf("lca(%d %d) = %d\n", a+1, b+1, c+1);
        paths[lx*2].h = paths[lx*2+1].h = hei[c];
        paths[lx*2].x = paths[lx*2+1].x = c;
        paths[lx*2].y = a, paths[lx*2+1].y = b;
    }

    sort(paths, paths+2*k);

    for(int lx = 0;lx < n;lx++) fat[lx] = lx;
   
    for(int lx = 0;lx < 2*k;lx++){
        int y = paths[lx].y, x = paths[lx].x;
        while(qfat(y) != qfat(x)){
            join(x, y);
            y = ac1[y];
        }
    }
   
    while(q--){
        int a, b; scanf("%d %d", &a, &b); a--, b--;
        printf("%d\n", qfat(a) == qfat(b));
    }

    return 0;
}


TIOJ 1799 . Richmen


環狀分錢問題,有點好奇推廣

0. 水母?
1. 仙人掌?
2. 2D?
3. 平面圖?
3. 一般圖?

#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef long long int int64;

int64 arr[5000010];

int main(){
    int64 n; scanf("%lld", &n);
    int64 avg = 0;
    arr[0] = 0;
    for(int lx = 1;lx <= n;lx++){
        scanf("%lld", arr+lx);
        avg += arr[lx];
        arr[lx] += arr[lx-1];
    }
    avg /= n;
    for(int lx = 1;lx < n;lx++)
        arr[lx] -= lx*avg;

    sort(arr, arr+n);
   
    n--;  
    for(int lx = n;lx >= 1;lx--)
        arr[lx] = arr[lx]-arr[lx-1];
   
    int64 ans = 0;
    for(int lx = 1;lx <= n;lx++){
        if(lx <= n/2) ans += lx*arr[lx];
        else ans += (n-lx+1)*arr[lx];
    }

    printf("%lld\n", ans);
    return 0;
}

TIOJ 1795 . 咕嚕咕嚕呱啦呱啦

給個簡單圖,邊權是0或1,問存不存在權重和k的生成樹。

#include <cstdio>
#include <cstdio>
#include <vector>

using namespace std;

struct pr{int x, y; pr(int _x = 0, int _y = 0):x(_x), y(_y){return;}};

struct djs{
    int ft[100000];
    djs(){
        for(int lx = 0;lx < 100000;lx++)
            ft[lx] = lx;
        return;
    }
    int query(int a){
        return ft[a] == a ? a : ft[a] = query(ft[a]);
    }
    void join(int a, int b){
        int fa = query(a), fb = query(b);
        ft[fa] = fb;
        return;
    }
};

djs dj0, dj1;

vector<pr> eg[2];

int main(){
    int n, m, k; scanf("%d %d %d", &n, &m, &k);
    for(int lx = 0;lx < m;lx++){
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        eg[c].push_back(pr(a-1, b-1));
    }
   
    for(pr aa : eg[0]) dj0.join(aa.x, aa.y);
   
    int prc = 0;
    for(pr aa : eg[1]){
        if(dj0.query(aa.x) == dj0.query(aa.y)) continue;
        dj0.join(aa.x, aa.y);
        dj1.join(aa.x, aa.y);
        prc++;
    }
   
    bool con = true;
    for(int lx = 1;lx < n and con;lx++)
        if(dj0.query(lx) != dj0.query(0))
            con = false;
    if(!con){
        puts("NIE");
        return 0;
    }

    for(pr aa : eg[1]){
        if(prc == k) break;
        if(dj1.query(aa.x) == dj1.query(aa.y)) continue;
        dj1.join(aa.x, aa.y);
        prc++;
    }

    puts(prc == k ? "TAK" : "NIE");
    return 0;
}
     


2015年5月16日 星期六

TIOJ 1101 . D.分「樹」


#include <cstdio>
#include <cstdlib>

struct frac{
    int a, b;
    frac(int _a, int _b): a(_a), b(_b){}
    void print(){printf("(%d, %d)", a, b);}
};

frac operator+(frac f1, frac f2){return frac(f1.a+f2.a, f1.b+f2.b);}

int main(){
    int p, q;
    for(;;){
        scanf("%d %d", &p, &q);
        if(!p&&!q) break;
        if(p == 1 and q == 1){puts("0/1");continue;}
        if(p == 1 and q == 2){puts("1/0");continue;}
        if(p == 2 and q == 1){puts("1/1");continue;}
        q--;
        frac l(0,1), m(1,1), r(1,0);
        for(int lx = p;lx>=3;lx--){
            if(q & (1<<(lx-3))) l = m;
            else r = m;
            m =(l+r);
            //l.print(); m.print(); r.print(); puts("");
        }
        printf("%d/%d\n", m.a, m.b);
    }
    return 0;
}

2015年5月10日 星期日

TIOJ 1105 . H.PS3

convexhull 2pointer



#include <algorithm>
#include <vector>
#include <cmath>
#include <utility>

using namespace std;

const double PI = acos(-1);
const double eps = 1e-10;

bool db_st(const double& a, const double& b){return a < b-eps;}
bool db_eq(const double& a, const double& b){return fabs(a-b)<eps;}

int sgn(double a){ return a<-eps ? -1 : a>eps;}

class pt{
public:
    double x, y;
    int id;
    pt(double _x = 0, double _y = 0):x(_x), y(_y){}
    double len()const{return sqrt(x*x + y*y);}
};

bool operator==(const pt& a, const pt& b){return sgn(a.x-b.x) == 0 and sgn(a.y-b.y) == 0;}
pt operator-(const pt& a, const pt& b){return pt(a.x - b.x, a.y - b.y);}
pt operator+(const pt& a, const pt& b){return pt(a.x + b.x, a.y + b.y);}
double operator^(const pt& a, const pt& b){return a.x*b.y - a.y*b.x;}

struct cpbyx{bool operator()(pt a, pt b){return a.x == b.x ? a.y < b.y : a.x < b.x;}};
vector<pt> ConvexHull(vector<pt> inp){
    vector<pt> bt_ret, tp_ret;
    sort(inp.begin(), inp.end(), cpbyx());
    auto it = unique(inp.begin(), inp.end());
    inp.resize(distance(inp.begin(), it));
    for(int lx = 0;lx < inp.size();lx++){
        pt v = inp[lx];
        for(int ly = (int)bt_ret.size()-1;ly>=1;ly--){
            if(sgn((bt_ret[ly]-bt_ret[ly-1])^(v-bt_ret[ly])) <= 0){
                bt_ret.pop_back();
            }else
                break;
        }
        bt_ret.push_back(v);
    }
    for(int lx = (int)inp.size()-1;lx>=0;lx--){
        pt v = inp[lx];
        for(int ly = ((int)tp_ret.size())-1;ly>=1;ly--)
            if(sgn((tp_ret[ly]-tp_ret[ly-1])^(v-tp_ret[ly])) <= 0)
                tp_ret.pop_back();
            else
                break;
        tp_ret.push_back(v);
    }
   
    vector<pt> ret;
    for(int lx = 0;lx < bt_ret.size();lx++)
        ret.push_back(bt_ret[lx]);
    for(int lx = 1;lx+1 < tp_ret.size();lx++)
        ret.push_back(tp_ret[lx]);
    return ret;
}

struct ans{ int xx, yy; ans(int _x, int _y):xx(_x), yy(_y){if(_x > _y) swap(xx, yy);}};
bool operator<(ans a1, ans a2){ return (a1.xx != a2.xx) ? a1.xx < a2.xx : a1.yy < a2.yy;}

int main(){
    int n;
    for(;;){
        scanf("%d", &n);
        if(n == 0) break;
        vector<pt> inp(n);
        for(int lx = 0;lx < n;lx++)
            scanf("%lf %lf", &inp[lx].x, &inp[lx].y), inp[lx].id = lx;
        inp = ConvexHull(inp);
        int ptr = 0;
        int sz = inp.size();
        double ll = 0, prell;
        ans aa(inp[0].id, inp[0].id);
        for(int lx = 0;lx < sz;lx++){
            prell = (inp[ptr]-inp[lx]).len();
            for(;ptr<sz;ptr++){
                ans _aa(inp[lx].id, inp[ptr].id);
                double nll = (inp[lx]-inp[ptr]).len();
                if(db_st(ll, nll) or (db_eq(ll, nll) and _aa < aa)){
                    aa = _aa;
                    ll = nll;
                }
                if(db_st(nll, prell)){
                    break;
                }
                prell = nll;
            }
            ptr--;
        }
        printf("%d %d\n", aa.xx, aa.yy);
    }
    return 0;
}

2015年5月8日 星期五

TIOJ 1093 . B.古力德

Least Cover Circle

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <vector>

using namespace std;

const double eps = 1e-7;
const double inf = 1e7;

bool db_eq(const double& a, const double& b){return fabs(a-b)<=eps;}
bool db_bt(const double& a, const double& b){return a>b+eps;}
bool db_st(const double& a, const double& b){return a+eps<b;}

struct pt{
    double x, y;
    pt(double _x = 0, double _y = 0): x(_x), y(_y){}
    double len()const{return sqrt(x*x+y*y);}
};

pt operator+(const pt& a, const pt& b){return pt(a.x+b.x, a.y+b.y);}
pt operator-(const pt& a, const pt& b){return pt(a.x-b.x, a.y-b.y);}
pt operator/(const pt& a, const double& r){return pt(a.x/r, a.y/r);}
double operator^(const pt& a, const pt& b){return a.x*b.y-a.y*b.x;}
pt operator~(const pt& a){return pt(a.y, -a.x);}

struct line{
    // ax + by + c = 0;
    double a, b, c;
    line(){
        a = 0, b = 0, c = 0;
    }
    line(const pt& m, const pt& s){
        a = m.y, b = -m.x;
        c = -(a*s.x+b*s.y);
    }
    pt m()const{
        return pt(-b, a);
    }
};

pt operator*(const line& l1, const line& l2){
    double det = l1.m()^l2.m();
    if(db_eq(det, 0)) return pt(inf, inf);
    double detx = -l1.c*l2.b+l2.c*l1.b;
    double dety =  l1.c*l2.a-l2.c*l1.a;
    return pt(detx/det, dety/det);
}

struct cir{
    pt o;
    double r;
    cir(const pt& _o = pt(), const double& _r = 0): o(_o), r(_r){}
    cir(const pt& pt1, const pt& pt2){o = (pt1+pt2)/2; r = (pt1-o).len();}
   
    cir(const pt& pt1, const pt& pt2, const pt& pt3){
        line l1 = line(~(pt2-pt1), (pt1+pt2)/2);
        line l2 = line(~(pt3-pt1), (pt1+pt3)/2);
        o = l1*l2;
        if(db_eq(o.x, inf)){
            double l12 = (pt1-pt2).len(),
                   l23 = (pt2-pt3).len(),
                   l13 = (pt3-pt1).len();
            if(db_eq(l12+l23,l13)) cir(pt1,pt3);
            else if(db_eq(l13+l23,l12)) cir(pt1,pt2);
            else if(db_eq(l12+l13,l23)) cir(pt2,pt3);
            else assert(0);
        }else{
            r = (o-pt1).len();
        }
    }
    bool has(const pt& p){ return db_bt((p-o).len(),r) == false;}
};

cir lcc2(vector<pt>& inp, int lim, const pt& pt1, const pt& pt2){
    cir ret(pt1, pt2);
    for(int lx = 0;lx < lim;lx++)
        if(ret.has(inp[lx]) == false)
            ret = cir(pt1, pt2, inp[lx]);
    return ret;
}

cir lcc1(vector<pt>& inp, int lim, const pt& pt){
    cir ret(inp[0], pt);
    for(int lx = 1;lx < lim;lx++)
        if(ret.has(inp[lx]) == false)
            ret = lcc2(inp, lx, pt, inp[lx]);
    return ret;
}

cir lcc(vector<pt>& inp){
    random_shuffle(inp.begin(), inp.end());
    cir ret(inp[0], inp[1]);
    for(int lx = 2;lx < inp.size();lx++)
        if(ret.has(inp[lx]) == false)
            ret = lcc1(inp, lx, inp[lx]);
    return ret;
}

int main(){
    int n, m;
    for(;;){
        scanf("%d %d", &n, &m);
        if(n == 0 and m == 0) break;
        vector<pt> inp(m);
        for(int lx = 0;lx < m;lx++)
            scanf("%lf %lf", &inp[lx].x, &inp[lx].y);
        printf("%.3f\n", lcc(inp).r);
    }
    return 0;
}

2015年5月2日 星期六

1092 . A.跳格子遊戲

#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

vector<int> tree[100000];

int n, m;

int val[100000];

int dfs(int id){
    if(val[id] != -1) return val[id];
    if(id == n) return 1;
    for(int lx = 0;lx < tree[id].size();lx++)
        if(dfs(tree[id][lx]))
            return val[id] = 0;
    return val[id] = 1;
}

int main(){
    for(;;){
        scanf("%d %d", &n, &m);
        if(n == 0 and m == 0) break;
        for(int lx = 0;lx < n;lx++)
            tree[lx].clear(), val[lx] = -1;
        for(int lx = 0;lx < m;lx++){
            int a, b; scanf("%d %d", &a, &b);
            tree[a-1].push_back(b-1);
        }
        char tmp[20];
        scanf("%s", tmp);
        puts((dfs(0)^(tmp[1]=='i')) ? "Moumou":"Mimi");
    }
    return 0;
}

2015年5月1日 星期五

NPSC 2003 高中組 初賽 D.運河



#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const double eps = 1e-8;

bool db_eq(const double& a, const double& b){return fabs(a-b) <= eps;}
bool db_ne(const double& a, const double& b){return fabs(a-b) > eps;}
bool db_bg(const double& a, const double& b){return a-b >= -eps;}
bool db_sg(const double& a, const double& b){return a-b <=  eps;}
bool db_s(const double& a, const double& b){return a-b <=  -eps;}
bool db_b(const double& a, const double& b){return a-b >  eps;}
bool db_z(const double& a){return fabs(a) < eps;}
bool db_nz(const double& a){return fabs(a) >= eps;}
bool db_pos(const double& a){return a>= eps;}
bool db_neg(const double& a){return a<=-eps;}

struct pt{ double x, y; pt(double _x = 0, double _y = 0): x(_x), y(_y){return;}};
pt operator+(const pt& a, const pt& b){return pt(a.x+b.x, a.y+b.y);}
pt operator-(const pt& a, const pt& b){return pt(a.x-b.x, a.y-b.y);}
double operator^(const pt& a, const pt& b){return a.x*b.y - a.y*b.x;}
pt operator~(const pt& a){return pt(a.y, -a.x);}
bool operator==(const pt& a, const pt& b){return db_eq(a.x,b.x) and db_eq(a.y,b.y);}

struct line{
    double a, b, c;
    line(pt m, pt p){
        a = m.y; b = -m.x;
        c = -a*p.x - b*p.y;
        return;
    }
    double len()const{return sqrt(a*a + b*b);}
    pt m()const{return pt(a, -b);}
};

struct ch_cpx{bool operator()(const pt& a, const pt& b){return db_ne(a.x, b.x) ? db_s(a.x, b.x) : db_s(a.y, b.y);}};

vector<pt> make_ch(vector<pt>& inp){
    sort(inp.begin(), inp.end(), ch_cpx());
    auto it = unique(inp.begin(), inp.end());
    inp.resize(distance(inp.begin(), it));
    int inpsz = inp.size();
   
    vector<pt> bt(inpsz), tp(inpsz);

    int btsz = 0, tpsz = 0;
    for(int lx = 0;lx < inpsz;lx++){
        while(btsz > 1 and db_pos((bt[btsz-2] - bt[btsz-1])^(inp[lx] - bt[btsz-1])))
            btsz--;
        bt[btsz++] = inp[lx];
    }
   
    for(int lx = inpsz-1;lx >= 0;lx--){
        while(tpsz > 1 and db_pos((tp[tpsz-2] - tp[tpsz-1])^(inp[lx] - tp[tpsz-1])))
            tpsz--;
        tp[tpsz++] = inp[lx];
    }

    vector<pt> ret;
    for(int lx = 0;lx < btsz;lx++) ret.push_back(bt[lx]);
    for(int lx = 1;lx < tpsz-1;lx++) ret.push_back(tp[lx]);
   
    return ret;
}

int eval(const vector<pt>& ch, const line& l){
    int acnt = 0, bcnt = 0;
    for(int lx = 0;lx < ch.size();lx++){
        double val = l.a*ch[lx].x + l.b*ch[lx].y + l.c;
        if(db_pos(val)) acnt++;
        if(db_neg(val)) bcnt++;
    }
    if(acnt and bcnt) return 2; //err
    if(acnt) return  1;
    if(bcnt) return -1;
    return 0;
}

double cal(const vector<pt>& cha, const vector<pt>& chb, line la, line lb){
    int val_aa = eval(cha, la);
    int val_ab = eval(cha, lb);
    int val_ba = eval(chb, la);
    int val_bb = eval(chb, lb);
    if(val_aa == 2 or val_ab == 2 or val_ba == 2 or val_bb == 2) return 0;
    if(val_aa == val_ba and val_aa != 0) return 0;
    if(val_ab == val_bb and val_ab != 0) return 0;
    if(db_nz(la.m()^lb.m())) return 0;
    double k = 0;
    if(db_nz(la.a)) k = lb.a/la.a;
    if(db_nz(la.b)) k = lb.b/la.b;
    return fabs(la.c*k-lb.c)/la.len();
}

int main(){
    int m, n;
    for(;;){
        scanf("%d %d", &m, &n);
        if(n == 0 and m == 0) break;
        vector<pt> ap(m), bp(n);
        for(int lx = 0;lx < m;lx++) scanf("%lf %lf", &ap[lx].x, &ap[lx].y);
        for(int lx = 0;lx < n;lx++) scanf("%lf %lf", &bp[lx].x, &bp[lx].y);
        ap = make_ch(ap);
        bp = make_ch(bp);
        double dis = 0;
        int sza = ap.size(), szb = bp.size();
        for(int lx = 0;lx < sza;lx++){
            for(int ly = 0;ly < szb;ly++){
                line la = line(~(ap[lx]-bp[ly]),ap[lx]);
                line lb = line(~(ap[lx]-bp[ly]),bp[ly]);
                dis = max(dis, cal(ap, bp, la, lb));
            }
        }
        // p2l
        for(int lx = 0;lx < sza and sza > 1;lx++){
            for(int ly = 0;ly < szb;ly++){
                line la = line(ap[lx]-ap[(lx+1)%sza], ap[lx]);
                line lb = line(ap[lx]-ap[(lx+1)%sza], bp[ly]);
                dis = max(dis, cal(ap, bp, la, lb));
            }
        }
        // l2p
        for(int lx = 0;lx < sza;lx++){
            for(int ly = 0;ly < szb and szb > 1;ly++){
                line la = line(bp[ly]-bp[(ly+1)%szb], ap[lx]);
                line lb = line(bp[ly]-bp[(ly+1)%szb], bp[ly]);
                dis = max(dis, cal(ap, bp, la, lb));
            }
        }
        //l2l
        for(int lx = 0;lx < sza and sza > 1;lx++){
            for(int ly = 0;ly < szb and szb > 1;ly++){
                line la = line(ap[lx]-ap[(lx+1)%sza], ap[lx]);
                line lb = line(bp[ly]-bp[(ly+1)%szb], bp[ly]);
                dis = max(dis, cal(ap, bp, la, lb));
            }
        }
        if(db_z(dis)) printf("IMPOSSIBLE\n");
        else printf("%.3f\n", dis);
    }
    return 0;
}

2015年4月21日 星期二

TIOJ 1156 . 5.高中運動會

我覺得我該停止寫水題._.

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int main(){
    int t, ans = 0; scanf("%d", &t);
    while(t--){
        int n; scanf("%d", &n);
        ans = __gcd(ans, n);
    }
    printf("%d\n", ans);
    return 0;

}

TIOJ 1044 . [Interactive] Guess My Number

#include <cstdio>
#include "lib1044.h"
int main(void){
    int n = Initialize();
    int mm = 1, MM = n;
    while(mm < MM){
        int test = (mm+MM)/2;
        if(Guess(test))
            MM = test;
        else
            mm = test+1;
    }
    Report(mm);
    return 0;

}

TIOJ 1833 . Problem B 陽炎眩亂

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

int fat[100001];

void init(int n){
    for(int lx = 0;lx < n;lx++)
        fat[lx] = lx;
    return;
}

int gfat(int a){
    return (fat[a] == a) ? a : fat[a] = gfat(fat[a]) ;
}

void join(int a, int b){
    int fa = gfat(a);
    int fb = gfat(b);
    fat[fb] = fa;
    return;
}

int main(){
    int n, q; scanf("%d %d", &n, &q);
    init(n);
    char buf[100];
    while(q--){
        scanf("%s", buf);
        if(buf[0] == 'M'){
            int a, b; scanf("%d %d", &a, &b);
            join(a-1, b-1);
        }else{
            int a; scanf("%d", &a);
            printf("%d\n", gfat(a-1)+1);
        }
    }
    return 0;

}

TIOJ 1832 . Problem A 和諧的共鳴頻率 Submit Status Ranklist Back to Problems List

#include <cstdio>
#include <cstdlib>

using namespace std;

typedef long long int int64;

int64 arr[1000001];

int main(){
    int n, q; scanf("%d %d", &n, &q);
    arr[0] = 0;
    for(int lx = 1;lx <= n;lx++){
        int64 inp;
        scanf("%lld", &inp);
        arr[lx] = arr[lx-1]^inp;
    }
    while(q--){
        int a, b; scanf("%d %d", &a, &b);
        printf("%lld\n", arr[a-1]^arr[b]);
    }
    return 0;

}

TIOJ 1043 . F.名偵探蚵男


#include <cstdio>
#include <cstdlib>
typedef long long int int64;
int main(){
    int n, p;
    for(;;){
        scanf("%d %d", &n, &p);
        if(n == 0 and p == 0) break;
        int64 cc[10001][2] = {{1}, {0}};
        int now = 0;
        for(int lx = 0;lx < n;lx++){
            int64 inp; scanf("%lld", &inp);
            for(int y = 0;y <= p;y++)
                cc[y][1^now] = 0;
            for(int y = 0;y <= p;y++)
                for(int k = 0;y+inp*k <= p;k++)
                    cc[y+inp*k][1^now] += cc[y][now];
            now ^= 1;
        }
        printf("%lld\n", cc[p][now]);
    }
    return 0;
}