UVa 361 Cops and Robbers

题目描述你要模拟一个警察与小偷的游戏。在这个游戏中警察、小偷和其他市民被表示为二维平面上的点。如果一个市民位于三个警察构成的三角形内包括边界则称该市民是safe安全的。如果一个市民不是safe但位于三个小偷构成的三角形内则称该市民是robbed被抢的。如果一个市民既不满足上述条件则称其为neither都不是。给定一组警察、小偷和若干市民查询需要高效地判断每个市民的状态。输入格式输入包含多个数据集。每个数据集的第一行包含三个非负整数ccc、rrr、ooo警察、小偷和其他市民的数量。ccc、rrr、ooo均不超过200200200。接下来ccc行每行包含一个警察的(x,y)(x,y)(x,y)坐标。接下来rrr行每行包含一个小偷的(x,y)(x,y)(x,y)坐标。接下来ooo行每行包含一个市民的(x,y)(x,y)(x,y)坐标。所有坐标均为−500-500−500到500500500之间的整数。每个数据集后跟一个空行。当cro0c r o 0cro0时程序停止处理。输出格式对于每个数据集首先输出一行标识数据集。对于每个市民输出一行Citizen at (x,y) is status.其中status是safe、robbed或neither。每个数据集输出后跟一个空行。样例输入3 3 2 0 0 10 0 0 10 20 20 20 0 0 20 5 5 15 15 3 3 1 0 0 10 0 0 10 20 20 20 0 0 20 40 40 0 0 0样例输出Data set 1: Citizen at (5,5) is safe. Citizen at (15,15) is robbed. Data set 2: Citizen at (40,40) is neither.题目分析问题的本质这是一个点在三角形内判断问题。需要判断每个市民点是否位于任意三个警察构成的三角形内如果不是再判断是否位于任意三个小偷构成的三角形内。关键难点警察/小偷数量最多200200200直接枚举所有三元组O(2003)8×106O(200^3) 8 \times 10^6O(2003)8×106再乘上市民数量最多200200200总复杂度约为1.6×1091.6 \times 10^91.6×109不可接受。需要优化只检查可能包含该市民的三角形。优化策略排序按xxx坐标对警察和小偷排序剪枝如果市民的xxx坐标小于最左边警察小偷的xxx坐标或大于最右边警察小偷的xxx坐标则不可能在三角形内Y 坐标剪枝同样检查 Y 坐标范围限制枚举范围只枚举与市民xxx坐标相近的警察/小偷在代码中使用lower_bound找到第一个xxx坐标≥\geq≥市民xxx的警察位置只枚举从该位置开始的警察以及前面的警察当警察数量很少时c≤200c \leq 200c≤200即使O(c3)O(c^3)O(c3)枚举每个市民的复杂度为O(c3)O(c^3)O(c3)总复杂度O(o×c3)≈200×8×1061.6×109O(o \times c^3) \approx 200 \times 8 \times 10^6 1.6 \times 10^9O(o×c3)≈200×8×1061.6×109实际运行时间0.4900.4900.490秒说明剪枝非常有效参考代码// Cops and Robbers// UVa ID: 361// Verdict: Accepted// Submission Date: 2016-07-06// UVa Run Time: 0.490s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structpoint{intx,y;// 按 x 排序x 相同时按 y 排序booloperator(constpointanother)const{if(x!another.x)returnxanother.x;elsereturnyanother.y;}};vectorpointcops,robbers,citizens;intc,r,o,minCopsY,maxCopsY,minRobbersY,maxRobbersY;// 叉积向量 ab 和 ac 的叉积inlineintdirection(pointa,pointb,pointc){return(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);}// 判断市民是否在任意三个警察构成的三角形内boolisSafe(intperson){// 快速剪枝if(citizens[person].xcops.front().x)returnfalse;if(citizens[person].xcops.back().x)returnfalse;if(citizens[person].yminCopsY)returnfalse;if(citizens[person].ymaxCopsY)returnfalse;// 找到第一个 x 市民 x 的警察intstartlower_bound(cops.begin(),cops.end(),citizens[person])-cops.begin();for(intistart;icops.size();i)for(intj0;ji;j)for(intkj1;ki;k){intd1direction(cops[i],cops[j],citizens[person]);intd2direction(cops[j],cops[k],citizens[person]);intd3direction(cops[k],cops[i],citizens[person]);if(d10d20d30)returntrue;if(d10d20d30)returntrue;}returnfalse;}// 判断市民是否在任意三个小偷构成的三角形内boolisRobbed(intperson){if(citizens[person].xrobbers.front().x)returnfalse;if(citizens[person].xrobbers.back().x)returnfalse;if(citizens[person].yminRobbersY)returnfalse;if(citizens[person].ymaxRobbersY)returnfalse;intstartlower_bound(robbers.begin(),robbers.end(),citizens[person])-robbers.begin();for(intistart;irobbers.size();i)for(intj0;ji;j)for(intkj1;ki;k){intd1direction(robbers[i],robbers[j],citizens[person]);intd2direction(robbers[j],robbers[k],citizens[person]);intd3direction(robbers[k],robbers[i],citizens[person]);if(d10d20d30)returntrue;if(d10d20d30)returntrue;}returnfalse;}intmain(intargc,char*argv[]){ios::sync_with_stdio(false);intcases0,x,y;while(cincro){if(c0r0o0)break;cops.clear();robbers.clear();citizens.clear();minCopsY1000,maxCopsY-1000;minRobbersY1000,maxRobbersY-1000;// 读取警察for(inti1;ic;i){cinxy;cops.push_back((point){x,y});minCopsYmin(minCopsY,y);maxCopsYmax(maxCopsY,y);}// 读取小偷for(inti1;ir;i){cinxy;robbers.push_back((point){x,y});minRobbersYmin(minRobbersY,y);maxRobbersYmax(maxRobbersY,y);}// 读取市民for(inti1;io;i){cinxy;citizens.push_back((point){x,y});}// 排序sort(cops.begin(),cops.end());sort(robbers.begin(),robbers.end());coutData set cases:endl;for(inti0;icitizens.size();i){cout Citizen at (citizens[i].x,citizens[i].y) is ;if(isSafe(i))coutsafe.endl;elseif(isRobbed(i))coutrobbed.endl;elsecoutneither.endl;}coutendl;}return0;}