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

2015年4月10日 星期五

POJ 1279 Art Gallery


半平面交

*記得注意^算子優先順序

    // note ^ operator 
    // * operator 
    
    #include <cstdio>
    #include <cstdlib>
    #include <vector>
    #include <cmath>
    #include <algorithm>
    #include <functional>
    
    using namespace std;
    
    template<class T>
    void pvec(vector<T> val){
        for(int lx = 0;lx < val.size();lx++){
            val[lx].print();
            printf(" ");
        }
        puts("");
        return;
    }
    
    const double eps = 1e-7;
    
    struct Point{
        double x, y;
        Point(double _x = 0, double _y = 0):x(_x), y(_y){}
        int id() const {
            if(x > 0 and y >= 0) return 0;
            if(y > 0 and x <= 0) return 1;
            if(x < 0 and y <= 0) return 2;
            if(y < 0 and x >= 0) return 3;
            return -1;
        }
        void print(){ printf("(%.2f,%.2f)", x, y); return; }
    };
    
    Point operator+(const Point& a, const Point& b){return Point(a.x + b.x, a.y + b.y);}
    Point operator-(const Point& a, const Point& b){return Point(a.x - b.x, a.y - b.y);}
    Point operator*(const Point& a, double k){return Point(a.x*k, a.y*k);}
    Point operator*(double k, const Point& a){return Point(a.x*k, a.y*k);}
    double operator*(const Point& a, const Point& b){return a.x*b.x + a.y*b.y;}
    double operator^(const Point& a, const Point& b){return a.x*b.y - a.y*b.x;}
    
    struct Line{
        Point p1, p2, dt;
        Line(Point a = Point(), Point b = Point()):p1(a), p2(b){dt = p2-p1;return;}
        void print(){ p1.print(); printf("->"); p2.print();}
    };
    
    bool IsParallel(const Line& a, const Line& b) { return fabs(a.dt^b.dt) < eps; }
    bool IsInPlane(const Line& a, const Point& p){ return (a.dt^(p-a.p1)) >= eps; }
    
    bool operator<(const Point& a, const Point& b){
        int ida = a.id(), idb = b.id();
        return (ida != idb) ? ida < idb : 0 < (a^b);
    }
    
    typedef vector<Point> Polygon;
    
    Point GetLineInterX(const Line& l1, const Line& l2){
        const Point &a1 = l1.p1, &a2 = l1.p2;
        const Point &b1 = l2.p1, &b2 = l2.p2;
        Point a = a2-a1, b = b2-b1, s = b1-a1;
        return a1 + a*((b^s)/(b^a));
    }
    
    bool lcmp(const Line& a, const Line& b){
        return (a.p2-a.p1) < (b.p2-b.p1);
    };
    
    Polygon GetPlaneInterX(vector<Line>& _inp){
        if(_inp.size() <= 2) return Polygon();
        sort(_inp.begin(), _inp.end(), lcmp);
        // deal with parellel part
        vector<Line> inp(1, _inp[0]);
        for(int lx = 1;lx < _inp.size();lx++){
            Line& prc_line = inp[(int)inp.size() - 1];
            if(IsParallel(prc_line, _inp[lx])){
                if(IsInPlane(prc_line, _inp[lx].p2))
                    prc_line = _inp[lx];
            }else
                inp.push_back(_inp[lx]);
        }
        int sz = inp.size();
        if(sz <= 2) return Polygon();
        
        int qs = 0, qe = 2;
        vector<Line> que(sz+1);
        que[0] = inp[0], que[1] = inp[1];
        for(int lx = 2;lx < sz;lx++){
            while(qe-qs >= 2 and not IsInPlane(inp[lx], GetLineInterX(que[qe-1], que[qe-2]))) qe--;
            while(qe-qs >= 2 and not IsInPlane(inp[lx], GetLineInterX(que[qs]  , que[qs+1]))) qs++;
            que[qe++] = inp[lx];
        }
    
        while(qe-qs >= 2 and not IsInPlane(que[qs]  , GetLineInterX(que[qe-1], que[qe-2]))) qe--;
        while(qe-qs >= 2 and not IsInPlane(que[qe-1], GetLineInterX(que[qs]  , que[qs+1]))) qs++;
        if(qe-qs <= 2) return Polygon();
    
        que[qe++] = que[qs];
        Polygon ret;
        for(int lx = qs;lx < qe-1;lx++)
            ret.push_back(GetLineInterX(que[lx], que[lx+1]));
     
        return ret;
    }
    
    double GetArea(Polygon a){
        if(a.size() == 0) return 0;
        double ret = 0;
        a.push_back(a[0]);
        for(int lx = 0;lx+1 < a.size();lx++)
            ret += a[lx]^a[lx+1];
        return ret/2;
    }
    
    int main(){
        int T; scanf("%d", &T);
        while(T--){
            Polygon hls;
            int n; scanf("%d", &n);
            for(int lx = 0;lx < n;lx++){
                Point inp;
                scanf("%lf %lf", &inp.x, &inp.y);
                hls.push_back(inp);
            }
            if(GetArea(hls) < 0) reverse(hls.begin(), hls.end());
            hls.push_back(hls[0]);
            vector<Line> par;
            for(int lx = 0;lx < n;lx++)
                par.push_back(Line(hls[lx], hls[lx+1]));
             
            Polygon getres = GetPlaneInterX(par);
    
            printf("%.2f\n", GetArea(getres));
    
        }
        return 0;
    }

2014年12月28日 星期日

POJ 3015 Expected Difference



卡(int64)超久== 一卡卡兩小時==

#include<cstdio>
#include<cstdlib>

long double arr[50001];
long double sig[50001];

int main(){
    int n, m;
    for(;;){
        scanf("%d %d", &n, &m);
        if(n + m == 0)
            break;

        arr[n] = m*(m-1)/(long double)((n-m+2)*(n-m+1));
        for(int lx = n-1;lx >= 0;lx--)
            arr[lx] = arr[lx+1]*(((lx+1)-(m-2))/((long double)(lx+1)));

        sig[0] = arr[0];
        for(int lx= 1;lx <= n;lx++)
            sig[lx] = sig[lx-1] + arr[lx];

        int val;
        long double ans= 0;
        for(int lx = 0;lx < n;lx++){
            scanf("%d", &val);
            long double gv = (long double) val;
            if(lx == 0)
                ans -= gv*sig[n-2];
            else
                ans -= gv*(sig[n-2-lx] - sig[lx-1]);
        }
        printf("%.3LF\n", ans);
    }
    return 0;
}

2014年11月25日 星期二

POJ 3481 Double Queue




#include<cstdio>
#include<cstdlib>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
int main(){
    int op, k, p;
    set<pii> que;
    for(;;){
        scanf("%d", &op);
        if(op == 0) break;
        if(op == 1){
            scanf("%d %d", &k, &p);
            que.insert(pii(p, k));
        }else if(op == 2){
            if(que.size() == 0)
                puts("0");
            else{
                set<pii>::iterator get = que.end();
                get--;
                printf("%d\n", get->second);
                que.erase(*get);
            }
        }else{
            if(que.size() == 0)
                puts("0");
            else{
                set<pii>::iterator get = que.begin();
                printf("%d\n", get->second);
                que.erase(*get);
            }
        }
    }
    return 0;
}

2014年10月31日 星期五

POJ 3469 Dual Core CPU

把常數壓一壓就好了

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
struct{int a, b, val;}lks[500000]; int lkcnt; int _n;
vector<int> to[30000]; int cur[30000];
void init(int n){
 lkcnt = 0;
 _n = n;
 for(int lx = 0;lx < n;lx++)
  to[lx].clear();
 return;
}
void addlink(int a, int b, int ab, int ba = 0){
 lks[lkcnt].a = a, lks[lkcnt].b = b, lks[lkcnt].val = ab; to[a].push_back(lkcnt++);
 lks[lkcnt].a = b, lks[lkcnt].b = a, lks[lkcnt].val = ba ; to[b].push_back(lkcnt++);
 return;
}
int dis[30000], que[30000];
int bfs(int s, int t){
 int n = _n;
 for(int lx = 0;lx < n;lx++) dis[lx] = -1;
 int qs = 0, qe = 1; dis[s] = 0, que[0] = s;
 while(qs < qe){
  int g = que[qs++];
  for(int lx = 0;lx < to[g].size();lx++){
   int lind = to[g][lx];
   int pind = lks[lind].b;
   if(dis[pind] != -1) continue;
   if(lks[lind].val == 0) continue;
   dis[pind] = dis[g] + 1;
   que[qe++] = pind;
  }
 }
 return dis[t] != -1;
}
bool vis[30000];
int dfs(int vv, int df, int s, int t){
 if(vv == t) return df;
 if(vis[vv]) return 0;
 vis[vv] = true;
 for(int& lx = cur[vv];lx < to[vv].size();lx++){
  int lind = to[vv][lx];
  int pind = lks[lind].b;
  if(lks[lind].val == 0) continue;
  if(dis[pind] != dis[vv]+1) continue;
  int f = dfs(pind, min(lks[lind].val, df), s, t);
  if(f > 0){
   lks[lind].val -= f;
   lks[lind^1].val += f;
   return f;
  }
 }
 return 0;
}
int dinic(int s, int t){
 int f = 0, df;
 while(bfs(s, t)){
  memset(cur, 0, sizeof(cur));
  for(;;){
   memset(vis, 0, sizeof(vis));
   df = dfs(s, 1000000000, s, t);
   if(df == 0) break;
   f += df;
  }
 }
 return f;
}
int main()
{
    int n, m, a, b, w;
    scanf("%d %d", &n, &m);
    init(n+2);
    for(int lx = 0;lx < n;lx++){
  scanf("%d %d", &a, &b);
  addlink(0, lx+1, a);
  addlink(lx+1, n+1, b);
    }
    for(int lx = 0;lx < m;lx++){
  scanf("%d %d %d", &a, &b, &w);
  addlink(a, b, w, w);
    }
    printf("%d\n", dinic(0, n+1));
 return 0;
}