SRM640,641 Div1E

んーなんかSRM641で無駄に時間を溶かしてつらかった

・SRM640 Div1E ChristmasTreeDecoration

n個の頂点とm個の辺が与えられる.各頂点には色がついていて,同じ色の頂点同士を結ぶ辺は好ましくない.いくつかの辺を選んでn頂点の木を作るとき,同じ色の頂点同士を結ぶ辺は最小何本か?という問題.

これは簡単.同じ色の頂点同士を結んでいるならコスト1,そうでないならコスト0としたときの最小全域木なのでクラスカル法とかをしてやる.

ソースコード

typedef pair<int,int> PI;
typedef pair<int,PI> E;
struct UnionFind {
    int *par;
    int *rank;
    int size;
    UnionFind(int n):size(n) {
        par=new int[size];
        rank=new int[size];
        for(int i=0;i<n;i++) {
            par[i]=i;
            rank[i]=0;
        }
    }
    int find(int x) {
        if(x==par[x]) return x;
        return par[x]=find(par[x]);
    }
    void unite(int x,int y) {
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]) {
            par[x]=y;
        }else {
            par[y]=x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }
    bool same(int x,int y) {
        return find(x)==find(y);
    }
};
class ChristmasTreeDecoration {
    public:
    int solve(vector<int> col, vector<int> x, vector<int> y) {
        E edge[200];
        int n=col.size();
        int m=x.size();
        for(int i=0;i<m;i++) {
            x[i]--;
            y[i]--;
            edge[i]=E(col[x[i]]==col[y[i]],PI(x[i],y[i]));
        }
        sort(edge,edge+m);
        UnionFind U(n);
        int ans=0;
        for(int i=0;i<m;i++) {
            int s=edge[i].second.first;
            int t=edge[i].second.second;
            if(U.same(s,t)) continue;
            U.unite(s,t);
            ans+=edge[i].first;
        }
        return ans;
    }
};

・SRM641 Div1E TrianglesContainOrigin

二次元平面上にn個の点がある.このうち3個の点を選んで出来る三角形であって,原点が三角形の内部にあるようなものはいくつあるか?という問題.

図を描いてかんがえてみると,3個のうち2個の頂点を固定すると,3個目の頂点はどの領域にないといけないかがわかる.各頂点を極座標で表したときの偏角を求めておく.i番目の頂点の偏角をarg[i]としよう(0≦arg[i]<2πで,argの昇順にソートされているとする).三角形の二つの頂点をi番目の頂点とj(j<i)番目の頂点とすると,3個目の頂点の偏角xはarg[i]+π<x<arg[j]+πでないといけない.二分探索でこの区間の長さが求まるので終わり.のはずなのだけど無限にTLEが取れなくて終わり.kmjpさんとか他の人のプログラムをなげてみたけどダメなので何かあるのかもしれない.

ソースコード(未AC)

int idx[2500];
class TrianglesContainOrigin {
    public:
    long long count(vector<int> x, vector<int> y) {
        int n=x.size();
        vector<double> v;
        for(int i=0;i<n;i++) {
            double d=atan2(y[i],x[i]);
            if(d<0) d+=2*PI;
            v.push_back(d);
        }
        sort(v.begin(),v.end());
        for(int i=0;i<n;i++) {
            idx[i]=lower_bound(v.begin(),v.end(),v[i]+PI)-v.begin();
        }
        LL ans=0;
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                if(v[j]>=v[i]+PI) break;
                ans+=idx[j]-idx[i];
            }
        }
        return ans;
    }
};