设为首页 加入收藏

TOP

计算几何 图论 网络流思想(一)
2012-11-04 13:52:18 来源: 作者: 【 】 浏览:856
Tags:计算 几何   图论 网络 思想

    题意: 给你一堆坐标点,然后告诉你他们之间的连接情况,所有的边都是双向的,并且图是连通的。边数,点数都是10w级别

    然后开始询问,每个询问是输入图中某个多边形的所有顶点,然后问你这个多边形内部一共有几个点(包括边界上的点)

    看完后就懂了,关键就是利用流的思想,当选定某个简单多边形的时候,内部的点数就等于流进去的流量和减去流出来的流量和,反正就是流量差,怎么定义很自由

    统计的时候不能暴力

    利用坐标的极角序处理出一个前缀和就可以很快得到答案

    具体见代码

    关于多边形的内部究竟在哪一侧还是搞了我很长时间,太纠结了

    [cpp]

    #include<cmath>

    #include<cstring>

    #include<cstdlib>

    #include<cstdio>

    #include<algorithm>

    #include<map>

    #include<set>

    #include<vector>

    using namespace std;

    #define MP make_pair

    #define PB push_back

    const int maxn  =  100010;

    const double inf = 1e10;

    struct Point {

    double x,y;

    Point(){};

    Point(double sx,double sy) : x(sx),y(sy){}

    }p[maxn];

    double operator / (const Point &b,const Point &a) {

    return atan2(b.y-a.y,b.x-a.x);

    }

    bool operator  <  (const Point &a,const Point &b){

    if(a.x!=b.x)

    return a.x<b.x;

    return a.y<b.y;

    }

    inline double cross(double x1,double y1,double x2,double y2){

    return x1*y2-x2*y1;

    }

    inline double chacha(Point s,Point a,Point b){

    return cross(a.x-s.x,a.y-s.y,b.x-s.x,b.y-s.y);

    }

    struct Edge{

    double ang;

    int to;

    Edge(){}

    Edge(double a,int t):ang(a),to(t){};

    bool operator < (const Edge &cmp) const{

    return ang<cmp.ang;

    }

    };

    vector<Edge> edge[maxn];

    map<pair<int,int>,int> sum,flow;

    int all[maxn];

    int n,m;

    inline void add_edge(int u,int v)

    {

    Edge k;

    k.to=v;k.ang=p[v]/p[u];

    edge[u].PB(k);

    flow[MP(u,v)]=0;

    }

    bool vis[maxn];

    int dfs(int u,int f)

    {

    vis[u]=true;

    int cnt=1;

    for(vector<Edge>::iterator it=edge[u].begin();it!=edge[u].end();it++)

    {

    int v=it->to;

   

首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇搜狐2012校园招聘会笔试题 下一篇ActiveX技术综述

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: