首页 > 代码库 > BZOJ 1035 Risk
BZOJ 1035 Risk
Description
经过连续若干年的推广，Risk这个游戏已经风靡全国，成为大众喜闻乐见的重要娱乐方式。Risk这个游戏可以理解为一种简易的策略游戏，游戏者的目的是占领所有的土地。由于游戏规则的规定，只要两个国家相邻，就认为两个国家有交战的可能性。我们现在希望知道在当前的局面下，哪些国家之间有交战的可能性。注意，我们认为只有当两个国家的国界线有公共边的时候才认为相邻，若两个国家的领土只有公共点，则认为两个国家不相邻。每一个国家的边界由一系列线段组成，保证这个边界是一个简单多边形，即严格不自交。为了定位每个国家的位置，我们还给出每个国家最庞大的一支军队的位置，保证这个位置一定出现在某一个形内，而不是出现在某条边界上。
Input
输入文件的第一行中包括两个整数n,m。分别表示地图上的国家数和描述国家的边界的线段的数量。1<=n<=600，1<=m<=4000。接下来n行，每行用一对数描述了某个国家的主力军队的坐标。接下来m行，每行有4个数x1,y1,x2,y2，（x1,y1）-(x2,y2)描述了一条国界线。所有点的坐标都是0-10000之间的整数。保证输入的所有线段至多只会在线段交点处相交。整张地图上有且仅有一块面积无限的空白区域不属于任何国家。每一条国界线两侧的区域或者隶属于两个不同的国家，或者分隔了一个国家与那块无穷大的空白区域。即保证一条国界线两侧的区域不同时属于同一个国家或是同时都是空白区域。所有封闭区域内部包含且仅包含一支主力军队，表示了该区域的归属。 
例如上图中第一行的数据是合法的。而第二行中的数据都是不合法的。左边的那幅图包含线段两侧都是空白区域；中间的图包含线段两侧区域同时属于同一个国家；右边的图中军队被布置在了国界线上，因此非法；此外若最右侧的图中若没有军队也是非法的。保证输入文件提供的数据都是合法的，你的程序不需要进行数据合法性的判定。
Output
包括n行，每行第一个数字x表示有x个国家可能与这个国家交战，接着在同一行中升序输出x个整数，表示可能与这个国家交战的国家的编号。国家按输入中给出的顺序从1到n编号。注意数字间严格以一个空格隔开，并且不要在行末输出多余的空白字符。
Sample Input
4 12
3 2
11 8
12 17
1 19
0 0 10 0
10 0 20 0
20 0 20 10
20 10 20 20
20 20 10 20
10 20 0 20
0 20 0 10
0 10 0 0
10 0 10 10
0 10 10 10
20 10 10 10
10 20 10 10
3 2
11 8
12 17
1 19
0 0 10 0
10 0 20 0
20 0 20 10
20 10 20 20
20 20 10 20
10 20 0 20
0 20 0 10
0 10 0 0
10 0 10 10
0 10 10 10
20 10 10 10
10 20 10 10
Sample Output
2 2 4
2 1 3
2 2 4
2 1 3
2 1 3
2 2 4
2 1 3
HINT
Source
Cerc2004
一个点定位裸题。
首先，我们要用最小左转法去找平面(将边拆成两条，按照极角序排序，每走到一个点就走他所走过的边的下一条边，直到走出一个环为止，所走出的边为一个平面)。但是有特殊情况要处理，比如平面套平面。因此，我们需要再处理一遍我们所得到的平面，消掉重复的平面。
然后，就是点定位了。点定位用扫描线平衡树离线做。将所有点按照x排序，从左往右扫过去：扫到一个做端点，将其所对应的线段加入平衡树中；扫到右端点，在平衡树中删除这条线段；扫到询问点，找到其所对应的高度的上一条线段。平衡树维护当前x坐标，线段的高低。实现有许多细节要处理，参见我写的code：
1 #include<iostream> 2 #include<cmath> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdio> 6 #include<cstdlib> 7 #include<queue> 8 #include<set> 9 using namespace std; 10 11 #define rhl (100000) 12 #define oo (1e5) 13 #define eps (1e-6) 14 #define maxm (8010) 15 int n,m,all,sum,tot,pos[maxm],have[maxm],cnt = 1; 16 double space[maxm]; bool exist[maxm]; 17 18 inline bool equal(double x,double y) { return fabs(x-y) <= eps; } 19 inline bool dd(double a,double b) { if (equal(a,b)) return true; return a >= b; } 20 inline bool xd(double a,double b) { if (equal(a,b)) return true; return a <= b; } 21 22 struct NODE 23 { 24 double x,y; 25 26 friend inline bool operator == (NODE p,NODE q) { return equal(p.x,q.x)&&equal(p.y,q.y); } 27 friend inline NODE operator -(NODE p,NODE q) { return (NODE) {p.x-q.x,p.y-q.y}; } 28 friend inline double operator /(NODE a,NODE b) { return a.x*b.y-b.x*a.y; } 29 inline NODE ra() 30 { 31 int xx,yy; 32 do xx = rand()%rhl,yy = rand()%rhl; 33 while (equal(1.0*xx,x)||equal(1.0*yy,y)); 34 return (NODE) {1.0*xx,1.0*yy}; 35 } 36 inline double angle() { return atan2(y,x); } 37 inline void read() { scanf("%lf %lf",&x,&y); } 38 }pp[maxm],army[maxm]; 39 40 struct LINE 41 { 42 double a,b,c; 43 inline bool on(NODE p) { return equal(0,a*p.x+b*p.y+c); } 44 }; 45 46 struct SEG 47 { 48 NODE a,b; 49 inline LINE extend() { return (LINE) {a.y-b.y,b.x-a.x,b.y*(a.x-b.x)-b.x*(a.y-b.y)}; } 50 inline bool on(NODE p) 51 { 52 if (p == a) return true; 53 if (p == b) return true; 54 return (dd(p.x,min(a.x,b.x))&xd(p.x,max(a.x,b.x)))&&(dd(p.y,min(a.y,b.y))&xd(p.y,max(a.y,b.y))); 55 } 56 }; 57 58 struct EDGE 59 { 60 int from,to,id,sur; 61 62 friend inline bool operator <(EDGE a,EDGE b) { return (pp[a.to]-pp[a.from]).angle() < (pp[b.to]-pp[b.from]).angle(); } 63 }edge[maxm]; 64 65 struct SCAN 66 { 67 double x,y; int bel,sign; 68 69 friend inline bool operator <(SCAN a,SCAN b) 70 { 71 if (a.x == b.x) return a.sign > b.sign; 72 return a.x < b.x; 73 } 74 }bac[maxm]; 75 76 struct SPLAY 77 { 78 int num,root,ch[maxm][2],fa[maxm],key[maxm]; queue <int> team; 79 80 inline int newnode() 81 { 82 int ret; 83 if (team.empty()) ret = ++num; 84 else ret = team.front(),team.pop(); 85 fa[ret] = ch[ret][0] = ch[ret][1] = 0; 86 return ret; 87 } 88 89 inline void init() 90 { 91 num = 0; root = newnode(); 92 key[root] = cnt; 93 } 94 95 inline void rotate(int x) 96 { 97 int y = fa[x],z = fa[y],l = ch[y][1] == x,r = l^1; 98 if (z != 0) ch[z][ch[z][1] == y] = x; 99 fa[x] = z; fa[y] = x; fa[ch[x][r]] = y;100 ch[y][l] = ch[x][r]; ch[x][r] = y;101 fa[0] = 0;102 }103 104 inline void splay(int x)105 {106 while (fa[x] != 0)107 {108 int y = fa[x],z = fa[y];109 if (fa[y] != 0)110 {111 if ((ch[y][0] == x)^(ch[z][0] == y)) rotate(x);112 else rotate(y);113 }114 rotate(x);115 }116 root = x;117 }118 119 inline int lower_bound(NODE p)120 {121 int now = root,ret = 0;122 while (now)123 {124 int k = key[now];125 if ((p-pp[edge[k].from])/(pp[edge[k].to]-pp[edge[k].from]) >= 0)126 ret = k,now = ch[now][0];127 else now = ch[now][1];128 }129 return ret;130 }131 132 inline int find(int w)133 {134 int now = root;135 double x = pp[edge[w].to].x,y = pp[edge[w].to].y;136 double ang = (pp[edge[w].to] - pp[edge[w].from]).angle();137 while (now)138 {139 int k = key[now];140 if (k == w) return now;141 NODE p = pp[edge[k].to] - pp[edge[k].from],q = pp[edge[k].from];142 double xx = x - q.x,yy = q.y+xx/p.x*p.y;143 if (equal(yy,y))144 {145 double t = p.angle();146 now = ch[now][ang < t];147 }148 else now = ch[now][y > yy];149 }150 }151 152 inline void erase(int w)153 {154 int p = find(w);155 while (ch[p][0] || ch[p][1])156 {157 if (ch[p][0])158 {159 rotate(ch[p][0]);160 if (p == root) root = fa[p];161 }162 else163 {164 rotate(ch[p][1]);165 if (p == root) root = fa[p];166 }167 }168 team.push(p);169 ch[fa[p]][ch[fa[p]][1] == p] = 0;170 fa[p] = 0;171 }172 173 inline void insert(int w)174 {175 int now = root,pre;176 double x = pp[edge[w].from].x,y = pp[edge[w].from].y;177 double ang = (pp[edge[w].to] - pp[edge[w].from]).angle();178 double xx,yy;179 while (true)180 {181 int k = key[now];182 NODE p = pp[edge[k].to] - pp[edge[k].from],q = pp[edge[k].from];183 xx = x - q.x,yy = q.y+xx/p.x*p.y;184 if (equal(yy,y))185 {186 double t = p.angle();187 pre = now,now = ch[now][ang > t];188 if (!now)189 {190 now = newnode(); fa[now] = pre;191 ch[pre][ang > t] = now; key[now] = w;192 break;193 }194 }195 else196 {197 pre = now,now = ch[now][y > yy];198 if (!now)199 {200 now = newnode(); fa[now] = pre;201 ch[pre][y>yy] = now; key[now] = w;202 break;203 }204 }205 }206 splay(now);207 }208 }S;209 vector <int> G[maxm],sp[maxm],ss[maxm],ans;210 set <int> con[maxm];211 212 inline void add(int a,int b)213 {214 ++cnt; G[a].push_back(cnt);215 edge[cnt] = (EDGE) {a,b};216 }217 218 inline int find(NODE p)219 {220 for (int i = 1;i <= all;++i) if (pp[i] == p) return i;221 pp[++all] = p; return all;222 }223 224 inline bool cmp(int a,int b) { return edge[a] < edge[b]; }225 226 inline NODE cp(LINE l1,LINE l2)227 {228 double a1 = l1.a,b1 = l1.b,c1 = l1.c;229 double a2 = l2.a,b2 = l2.b,c2 = l2.c;230 double ry = (c2*a1-c1*a2)/(b1*a2-b2*a1),rx = (c1*b2-c2*b1)/(b1*a2-b2*a1);231 return (NODE) {rx,ry};232 }233 234 inline bool para(LINE l1,LINE l2) { return equal(l1.a * l2.b,l1.b * l2.a); }235 236 inline bool okay(int a,int b)237 {238 int nn2 = sp[b].size(),nn1 = sp[a].size(),cro;239 NODE p,q; SEG s,t; LINE l,l1;240 for (int i = 0;i < nn2;++i)241 {242 p = pp[sp[b][i]]; q = p.ra();243 s = (SEG) {p,q}; l = s.extend();244 cro = 0;245 for (int j = 0;j < nn1;++j)246 {247 t = (SEG) {pp[sp[a][j]],pp[sp[a][(j+1)%nn1]]};248 l1 = t.extend();249 if (l1.on(p)&&t.on(p)) return false;250 if (para(l,l1)) continue;251 q = cp(l,l1);252 if (dd(q.x,p.x)&&t.on(q)) ++cro;253 }254 if (!(cro&1)) return false;255 }256 return true;257 }258 259 inline void find_surface()260 {261 for (int i = 1;i <= all;++i) sort(G[i].begin(),G[i].end(),cmp);262 for (int i = 1;i <= all;++i)263 {264 int nn = G[i].size();265 for (int j = 0;j < nn;++j) edge[G[i][j]].id = j;266 }267 for (int i = 2;i <= cnt;++i)268 if (!edge[i].sur)269 {270 ++tot; int j = i,p,nn; double res = 0;271 while (!edge[j].sur)272 {273 edge[j].sur = tot; p = edge[j].to;274 sp[tot].push_back(p); ss[tot].push_back(j);275 j ^= 1; nn = G[p].size();276 j = G[p][(edge[j].id+1)%nn];277 }278 nn = sp[tot].size();279 for (j = 0;j < nn;++j)280 res += (pp[sp[tot][j]]-pp[sp[tot][0]])/(pp[sp[tot][(j+1)%nn]]-pp[sp[tot][0]]);281 res /= 2; space[tot] = res;282 }283 space[0] = -1e12;284 for (int i = 1;i <= tot;++i)285 if (!exist[i]&&space[i] > 0)286 {287 int in = 0;288 for (int j = 1;j <= tot;++j)289 if (!exist[j]&&space[j]<0&&space[j]>space[in])290 if (okay(j,i)) in = j;291 if (in)292 { 293 exist[i] = true;294 int nn = ss[i].size();295 for (int j = 0;j < nn;++j) edge[ss[i][j]].sur = in;296 }297 }298 for (int i = 2;i <= cnt;i += 2)299 {300 if (space[edge[i].sur] <= 0&&space[edge[i^1].sur] <= 0)301 {302 con[edge[i].sur].insert(edge[i^1].sur);303 con[edge[i^1].sur].insert(edge[i].sur);304 }305 }306 }307 308 inline void locate()309 {310 for (int i = 1;i <= n;++i)311 bac[++sum] = (SCAN) { army[i].x,army[i].y,i,0 };312 for (int i = 2;i <= cnt;i += 2)313 {314 if (equal(pp[edge[i].from].x,pp[edge[i].to].x)) continue;315 bac[++sum] = (SCAN) { pp[edge[i].from].x,pp[edge[i].from].y,i,1 };316 bac[++sum] = (SCAN) { pp[edge[i].to].x,pp[edge[i].to].y,i,2 };317 }318 pp[++all] = (NODE) {-oo,-oo}; pp[++all] = (NODE) {oo,-oo};319 edge[++cnt] = (EDGE) {all-1,all};320 sort(bac+1,bac+sum+1);321 S.init();322 for (int i = 1;i <= sum;++i)323 {324 if (bac[i].sign == 0) pos[bac[i].bel] = edge[S.lower_bound((NODE) {bac[i].x,bac[i].y})].sur;325 else if (bac[i].sign == 1) S.insert(bac[i].bel);326 else S.erase(bac[i].bel);327 }328 }329 330 inline void solve()331 {332 for (int i = 1;i <= n;++i) have[pos[i]] = i;333 for (int i = 1;i <= n;++i)334 {335 ans.clear();336 set <int> :: iterator it;337 for (it = con[pos[i]].begin();it != con[pos[i]].end();++it)338 ans.push_back(have[*it]);339 sort(ans.begin(),ans.end());340 int nn = ans.size();341 printf("%d",nn);342 for (int j = 0;j < nn;++j) printf(" %d",ans[j]);343 putchar(‘\n‘);344 }345 }346 347 int main()348 {349 freopen("1035.in","r",stdin);350 freopen("1035.out","w",stdout);351 srand(233);352 scanf("%d %d",&n,&m);353 for (int i = 1;i <= n;++i) army[i].read();354 for (int i = 1;i <= m;++i)355 {356 NODE p,q; p.read(); q.read();357 int a = find(p),b = find(q);358 if (p.x > q.x) swap(a,b);359 add(a,b); add(b,a);360 }361 find_surface();362 locate();363 solve();364 fclose(stdin); fclose(stdout);365 return 0;366 }
BZOJ 1035 Risk
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。