SGU 219 Synchrograph 6/10

想了一想，一個有>0值的環，或一個沒有入度的都可以不斷不斷的燃燒

環是可以循環燃燒，沒有入度的則可以無限燃燒

唯一會燒不起來的好像就是全部都是0的環所以就用0邊做出新的圖，用SCC判斷一下誰不能燒

而且如果有一個人的上游是無法亂燒的，那他就也不能亂燒（也就是所謂的alive）所以要再DFS一下，他的下游是誰

我想到一個比較好的解釋方式：
1. 對零的邊的SCC縮點，縮起來的那個點代表他無法燃燒
2. 因為他沒辦法燃燒，所以他下游的點也都不能燃燒
3. 但假設你把1,2,所說的點去除掉之後，剩下的點再做縮點，（因為環可以不斷的循環，所以可以視為是一個點）
4. 最後變成了DAG，一定存在一個無入度點，他可以無限燃燒，所以剩下的那些點，都是alive的。

//By momo
#include
#include
#include
#define N 1010
#define PB push_back
#define SZ(x) ((int)(x).size())
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

int n, m, hit[N], cnt, vst[N];
vector<int> G[N], rG[N], tG[N], scc[N];
void dfs(int p){
    vst[p] = 1;
    FOR(it, G[p])
        if(!vst[*it]) dfs(*it);
    hit[cnt++] = p;
}
void rdfs(int p){
    vst[p] = 1;
    FOR(it, rG[p])
        if(!vst[*it]) rdfs(*it);
    scc[cnt].PB(p);
}
void kosaraju(){
    cnt = 0; fill(vst, vst + n, 0);
    for(int i = 0; i < n; i++)
        if(!vst[i]) dfs(i);
    cnt = 0; fill(vst, vst + n, 0);
    for(int i = n-1; i >= 0; i--)
        if(!vst[hit[i]]) rdfs(hit[i]), cnt++;
}

int dead[N];
void ddfs(int p){
    vst[p] = 1;
    FOR(it, tG[p])
        if(!vst[*it]) ddfs(*it);
    dead[p] = 1;
}

int main (){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < m; i++){
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        a--, b--; if(c == 0) G[a].PB(b), rG[b].PB(a);
        if(a == b && c == 0) dead[a] = 1; tG[a].PB(b);
    }
    kosaraju();
    for(int i = 0; i < cnt; i++){
        if(SZ(scc[i]) == 1) continue;
        FOR(it, scc[i]) dead[*it] = 1;
    }
    fill(vst, vst+n, 0);
    for(int i = 0; i < n; i++)
        if(!vst[i] && dead[i]) ddfs(i);
    for(int i = 0; i < n; i++)
        printf("%d\n", 1 - dead[i]);
}

SGU 213 Strong Defence 6/10

還不錯的題目

先發現：

答案小於等於S-T的最短路長度L

（證明很簡單）

把從最短距X到X-1的設為一組邊集合

這樣總共有L個集合

因為X只能走到X或X-1，所以

這樣是一組合理解！

科科，證完了～

SGU 217 Two Cylinders 5/10

先做出積分式

接下來對其做數值模擬

因為精度的關係，這邊要使用一個稱為

『辛普森公式』的數值模擬方法

選三個點，用二次函數去fit他

接著就去算這曲線的面積，最後把這些東東全部加起來

寫的漂亮一點，可以弄成公式：

dx/3*(y0+4y1+2y2+…+2yn-2+4yn-1+yn)

//By momo
#include
#include
#include
#include
#define N 1000000
using namespace std;

double r1, r2, ans = 0;
double f(double x){
    return 8*sqrt((r1*r1-x*x)*(r2*r2-x*x));
}

int main (){
    scanf("%lf%lf", &r1, &r2);
    if(r1 > r2) swap(r1, r2);
    double dx = r1/N;
    for(int i = 0; i <= N; i++){
        double coe;
        if(i == 0 || i == N) coe = 1;
        else coe = (i&1)?4:2;
        ans += coe*dx*f(dx*i)/3;
    }
    printf("%.4lf\n", ans);
}

SGU 185 Two shortest 5/10

就是隨便弄，但他有卡記憶體

所以你先弄個dijkstra，把邊刪一刪

順便就把題目變成了最大流

流一流，然後再做兩次遍歷就結束了

重點就是不要用vector，容易MLE！

隨便開個陣列就好了。

因為他的N小小的，所以O(N^2)沒差

//By momo
#include
#include
#include
#include

#define N 410
#define INF 9000000
#define PB push_back
#define SZ(x) (int)(x).size()
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)

using namespace std;

int n, m, vst[N], dis[N], tbl[N][N], che[N][N];
bool dfs(int p){
    vst[p] = 1; if(p == n) return 1;
    for(int i = 1; i <= n; i++)
        if(!vst[i] && tbl[p][i] && dfs(i))
            return tbl[p][i] = 0, tbl[i][p] = 1, 1;
    return 0;
}

bool print(int p){
    if(p == n) return printf("%d\n", p), 1;
    printf("%d ", p);
    for(int i = 1; i <= n; i++)
        if(!tbl[p][i] && che[p][i] && print(i))
            return che[p][i] = 0, 1;
    return 0;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            tbl[i][j] = INF;
    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        tbl[a][b] = tbl[b][a] = c;
    }
    fill(vst, vst+n+1, 0);
    fill(dis, dis+n+1, INF); dis[1] = 0;
    while(1){
        int mn = INF, x = 0;
        for(int i = 1; i <= n; i++)
            if(mn > dis[i] && !vst[i]) mn = dis[i], x = i;
        if(mn == INF) break; vst[x] = 1;
        for(int i = 1; i <= n; i++)
            dis[i] = min(dis[x]+tbl[i][x], dis[i]);
    }
    for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++)
        tbl[i][j] = che[i][j] =
        (tbl[i][j] != INF && dis[i]+tbl[i][j] == dis[j]);
    for(int i = 0; i < 2; i++){
        fill(vst, vst+n+1, 0);
        if(dfs(1) == 0) return puts("No solution"), 0;
    }
    print(1); print(1);
}

SGU 198 Get Out! 6/10

好玩的題目

首先，把你的圓形船變成點，其他人膨脹(+sr)

接著如果兩個圓相交，就連一條線

如果你被包在一個封閉多邊形，你就出不去了

這邊有一個很有趣的性質：

線相交所產生的點圍出的環可以由這些島圍出更大的

（你就假設有個點，他可以把別人圍起來，弄一弄就發現可以用那些島的點圍起來）

有了這個特性，你只要判斷島點圍出的還即可(N個)

接下來，你先隨機弄一個射線（判斷是否在內）

看跟誰交在一起，接著你就用dfs走過這些點一遍

如果有back edge，你就判斷有沒有被關起來這樣

可以知道這樣就可以了，不需要去判斷所有的環

（因為要不是會重複，就是可以用已判斷過的環去組出來，所以完全不影響結果）

//By momo
#include
#include
#include
#include
#define N 310
#define EPS 1e-8
#define FOR(it, c) for(typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

vector<int> G[N];
int n, dfn[N], ttl[N], tbl[N][N], fl = 1;

struct cord{
    double x, y, r;
}s, e, t[N];

double tx[N], ty[N], tr[N];
double sq(double d){ return d*d; }
double dis(int a, int b){
    return sqrt(sq(t[a].x-t[b].x)+sq(t[a].y-t[b].y));
}
double crs(cord a, cord b, cord c){
    double vx = a.x-c.x, vy = a.y-c.y;
    double ux = b.x-c.x, uy = b.y-c.y;
    return vx * uy - ux * vy;
}
bool hit(int a, int b){
    if(crs(t[b], s, t[a]) * crs(t[b], e, t[a]) < EPS
    && crs(   s, t[a], e) * crs(   s, t[b], e) < EPS) return 1;
    return 0;
}

void dfs(int p, int f, int l, int sum){
    dfn[p] = l; ttl[p] = sum;
    FOR(it, G[p]){
        if(*it == f) continue;
        if(dfn[*it] == -1) dfs(*it, p, l+1, sum+tbl[p][*it]);
        else if(dfn[*it] < dfn[p]){
            int cnt = sum - ttl[*it] + tbl[*it][p];
            if(cnt % 2) fl = 0;
        }
    }
}

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%lf%lf%lf", &t[i].x, &t[i].y, &t[i].r);
    scanf("%lf%lf%lf", &s.x, &s.y, &s.r);
    e.x = 214748364.3654427, e.y = -12923.1793283;
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(dis(i, j)+EPS < t[i].r + t[j].r + 2*s.r){
                G[i].push_back(j);
                G[j].push_back(i);
                tbl[i][j] = tbl[j][i] = hit(i, j);
            }
        }
    }
    fill(dfn, dfn+n, -1);
    for(int i = 0; i < n; i++)
        if(dfn[i] == -1) dfs(i, -1, 0, 0);
    puts(fl?"YES":"NO");
}

SGU 192 RGB 6/10

只能用兩個字來形容：『麻煩』
但我越來越喜歡計算幾何搭配其他演算法的題目了

所以要想一個簡單的寫法是很重要的

一開始寫了一個很爛的方法，觀看了他人的作法後發現：

其實我們可以對每一條線段，枚舉每個其他線段遮住該線段的位置

『注意！我原本用的是沒被遮住的，但這樣一個線段就會產生多個線段，不好實現』

因為是遮住，你會發現每一個線段只會產生一條，很容易實現

可是這樣的話就會出現遮住的有重疊的情形，這時先sort，然後用很simple的greedy解決即可

而且找重疊的部份實在很簡單，min, max一下即可

O(n^2lgn)

//By momo
#include
#include
#define N 310
#define EPS 1e-7
using namespace std;

double fabs(double x){ return x<0?-x:x; }
bool same(double a, double b){ return a <= b+EPS && a+EPS >= b; }

struct cord{ double x, y; }S[N];
struct segm{ cord s, e; double m, b; int c; }L[N];
bool comp(cord a, cord b){ return a.x < b.x; }

int n;
void input(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++ i){
        char s[3];
        scanf("%lf%lf%lf%lf%s", &L[i].s.x, &L[i].s.y, &L[i].e.x, &L[i].e.y, s);
        if(same(L[i].s.x, L[i].e.x)){ --i, --n; continue; }
        L[i].c = (s[0] == 'R'? 0: (s[0] == 'G'? 1: 2));
        if(L[i].s.x > L[i].e.x) swap(L[i].s, L[i].e);
        L[i].m = (L[i].e.y - L[i].s.y) / (L[i].e.x - L[i].s.x);
        L[i].b = L[i].s.y - (L[i].m * L[i].s.x);
    }
}

void solve(){
    static double ans[4];
    for(int i = 0; i < n; i++){
        cord s, e; double sy2, ey2, tot = L[i].e.x-L[i].s.x; int cnt = 0;
        for(int j = 0; j < n; j++) if(i != j){
            s.x = max(L[i].s.x, L[j].s.x), e.x = min(L[i].e.x, L[j].e.x);
            s.y = s.x * L[i].m + L[i].b, sy2 = s.x * L[j].m + L[j].b;
            e.y = e.x * L[i].m + L[i].b, ey2 = e.x * L[j].m + L[j].b;
            if(s.x+EPS >= e.x || same(s.x, e.x)) continue;
            if(sy2+EPS >= s.y && ey2+EPS >= e.y) continue;
            if(s.y+EPS >= sy2 && e.y+EPS >= ey2) S[cnt].x = s.x, S[cnt++].y = e.x;
            else{
                bool v = (s.y+EPS >= sy2);
                double mid = (L[j].b-L[i].b) / (L[i].m-L[j].m);
                S[cnt].x = v?s.x:mid, S[cnt++].y = v?mid:e.x;
            }
        }
        sort(S, S+cnt, comp);
        if(cnt == 0){ ans[L[i].c] += tot; continue; }
        double stt = S[0].x, end = S[0].y;
        for(int j = 1; j < cnt; j++){
            if(end < S[j].x+EPS){
                tot -= end-stt;
                stt = S[j].x;
            }
            end = max(end, S[j].y);
        }ans[L[i].c] += tot-end+stt;
    }
    printf("R %.2lf\nG %.2lf\nB %.2lf\n", ans[0], ans[1], ans[2]);
}

int main(){ input(); solve(); }

SGU 190 Dominoes 4/10

先看看這個題目：

試證明想要在一個N*N但是對角的兩格不見了的棋盤
用2*1的塊體完整覆蓋是不可能的。

像這樣
OOX
OOO
XOO

首先N是奇數很簡單，但N是偶數怎麼辦呢？
其實你知道一個2*1的塊體一定會覆蓋到黑色跟白色（想想棋盤）
而黑色跟白色數目不等，所以當然不可能囉！

====================================

根據上題的概念，就可以發現這題很簡單

但仍然是一題有趣的題目

很明顯就是要做配對，而且要是完全配對

因為他是二分圖，所以弄一弄就解決囉～

//By momo
#include
#include
#include
#include

#define N 45
#define PB push_back
#define SZ(x) (int)(x).size()
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)

using namespace std;

vector<int> G[N*N], ans1, ans2;
int n, m, tbl[N][N], mch[N*N], vst[N*N];
void add_edge(int a, int b){ G[a].PB(b), G[b].PB(a); }

void Input(){
    scanf("%d%d", &n, &m);
    for(int i = 0, x, y; i < m; i++){
        scanf("%d%d", &x, &y);
        tbl[x-1][y-1] = 1;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0, x, y; j < n; j++){
            if(tbl[i][j]) continue;
            x = i+0, y = j+1;
            if(x < n && y < n && !tbl[x][y]) add_edge(i*n+j, x*n+y);
            x = i+1, y = j+0;
            if(x < n && y < n && !tbl[x][y]) add_edge(i*n+j, x*n+y);
        }
    }
}

bool Bi(int p){
    vst[p] = 1;
    FOR(it, G[p]){
        int w = mch[*it];
        if(w == -1 || !vst[w] && Bi(w)){
            mch[*it] = p;
            return 1;
        }
    }
    return 0;
}

void make(int i, int j){
    int x  = i/n, y  = i%n;
    int xx = j/n, yy = j%n;
    if(x+y > xx+yy) swap(x, xx), swap(y, yy);
    if(x < xx) ans1.PB(x*n+y);
    else ans2.PB(x*n+y);
}

void Solve(){
    int cnt = 0;
    memset(mch, -1, sizeof(mch));
    if((n*n - m) % 2){ puts("No"); return; }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        if(tbl[i][j] || (i+j) % 2 == 0) continue;
        memset(vst, 0, sizeof(vst)); if(Bi(i*n+j)) cnt++;
    }
    if(cnt != (n*n - m) / 2){ puts("No"); return; }
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){
        if(tbl[i][j] || (i+j) % 2 == 1) continue;
        int x = mch[i*n+j]; make(i*n+j, x);
    }
    puts("Yes");
    printf("%d\n", SZ(ans1));
    for(int i = 0; i < SZ(ans1); i++)
        printf("%d %d\n", ans1[i]/n+1, ans1[i]%n+1);
    printf("%d\n", SZ(ans2));
    for(int i = 0; i < SZ(ans2); i++)
        printf("%d %d\n", ans2[i]/n+1, ans2[i]%n+1);
}

int main(){
    Input();
    Solve();
}