题意: 给你一堆坐标点,然后告诉你他们之间的连接情况,所有的边都是双向的,并且图是连通的。边数,点数都是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;