P1227 完美的对称【洛谷算法习题】

P1227 完美的对称网页链接P1227 完美的对称题目描述在峰会期间必须使用许多保镖保卫参加会议的各国代表。代表们除了由他自己的随身保镖保护外组委会还指派了一些其他的特工和阻击手保护他们。为了使他们的工作卓有成效使被保卫的人的安全尽可能得到保障保镖被分配到被保护人的各个方向。保镖的最佳站立位置应该是这样的被保护人应站在所有保镖的对称中心。但是只要被保护人一移动保镖就很难根据要人的新位置调整位置。大多数的特工都很难对此作出实时调整。因此安全部长决定将该过程逆转一下保镖先站好自己的位置然后要人在他们的对称中心找到合适的位置。如果要人随便走动我们就对他的安全不必负责。你的工作是使这个过程自动操作。给出一组N NN个点保镖的位置你要找出它们的对称中心S SS在这儿被保护人将相对安全。下面以此类推。首先我们给定一点A AA以及对称中心S SS点A ′ AA′是点A AA以S SS为对称中心形成的像点即点S SS是线段A A ′ AAAA′的对称中心。点阵组X XX以S SS为中心的像点是由每个点的像点组成的点阵组。X XX是用来产生对称中心S SS的即点阵X XX以S SS为中心的像点的集合即为点阵X XX本身。输入格式输入文件第一行是一个整数N NN1 ≤ N ≤ 20000 1\le N\le 200001≤N≤20000接下来的N NN行每行包含用空格隔开的两个整数X i X_iXi​和Y i Y_iYi​− 10 5 ≤ X i , Y i ≤ 10 5 -10^5\le X_i,Y_i\le 10^5−105≤Xi​,Yi​≤105表示这组点阵中第i ii个点的笛卡尔坐标值。因为任何两个保镖都不会站在同一个位置上所以在给定的作业中任何两点都不相同。但注意保镖可以站在被保护人相同的位置。输出格式输出文件仅有一行。如果给定的点阵能产生一个对称中心则输出V.I.P. should stay at ( x , y ). \texttt{V.I.P. should stay at (}x\texttt{,}y\texttt{).}V.I.P. should stay at (x,y).其中x xx和y yy代表中心的笛卡尔坐标值格式为四舍五入保留至小数点后一位。如果该组点阵无对称中心输出This is a dangerous situation!注意输出时除了两个单词之间用一个空格隔开外不要输出多余空格。输入输出样例 #1输入 #18 1 10 3 6 6 8 6 2 3 -4 1 0 -2 -2 -2 4输出 #1V.I.P. should stay at (2.0,3.0).说明/提示JSOI2008 第二轮。解题思路本题核心是点集中心对称判定 排序验证快速求解对称中心。若点集存在中心对称点对称中心必然是排序后首尾两点的中点最外侧点两两对称。解题步骤首先将所有点按坐标排序固定首尾点的中点为候选对称中心随后遍历点集验证第i个点与第n-i1个点是否均关于该候选中心对称若所有点对均满足对称条件则该点为合法中心否则点集无对称中心。算法时间复杂度为O ( n log ⁡ n ) O(n\log n)O(nlogn)主要来自排序完美适配n ≤ 20000 n≤20000n≤20000的数据规模验证过程为线性遍历高效稳定。总结核心逻辑利用中心对称性质通过排序确定候选中心逐点验证对称性。关键操作点坐标排序、候选中心计算、对称点对校验。效率保障排序线性遍历时间复杂度低轻松处理大数据量的点集。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;structP{doublex,y;};boolcmp(Pu,Pv){if(u.yv.y)returnu.xv.x;returnu.yv.y;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);coutfixedsetprecision(1);ll n;cinn;vectorPa(n1);for(ll i1;in;i)cina[i].xa[i].y;sort(a.begin()1,a.end(),cmp);doublecx(a[1].xa[n].x)/2.0;doublecy(a[1].ya[n].y)/2.0;for(ll i2;in/2;i){doubletx(a[i].xa[n-i1].x)/2.0;doublety(a[i].ya[n-i1].y)/2.0;if(cx!tx||cy!ty){coutThis is a dangerous situation!;return0;}}coutV.I.P. should stay at (cx,cy).;return0;}