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

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;

}

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

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

HDUOJ 4720 Naive and Silly Muggles

#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;}
bool db_be(const double& a, const double& b){return a>=b-eps;}
bool db_se(const double& a, const double& b){return a<=b+eps;}

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

int main(){
    int T; scanf("%d", &T);
    for(int lt = 1;lt <= T;lt++){
        pt p[4],tt;
        for(int lx = 0;lx<4;lx++)
            scanf("%lf %lf", &p[lx].x, &p[lx].y);
        cir cc(p[0],p[1],p[2]);
        cir c01(p[0], p[1]);
        cir c12(p[1], p[2]);
        cir c02(p[0], p[2]);
        if(c01.has(p[2]) and db_st(c01.r, cc.r)) cc = c01;
        if(c02.has(p[1]) and db_st(c02.r, cc.r)) cc = c02;
        if(c12.has(p[0]) and db_st(c12.r, cc.r)) cc = c12;
        
        printf("Case #%d: %s\n", lt, cc.has(p[3])==false ? "Safe":"Danger");
    }
    return 0;
}

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

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