网站中文域名好吗,石家庄最新轨迹,90设计网站是不是没有视频模板,单位门户网站建设的请示题解-P9658 Laser Trap
题目传送门
题意简述
题面是英文的#xff0c;还没翻译#xff0c;就讲一讲吧。 n n n 个激光发射器#xff0c;两两之间产生激光束#xff0c;将平面分为若干区域。 问至少删去多少个发射器#xff0c;可以使得原点与外侧区域联通。 多组数据还没翻译就讲一讲吧。 n n n 个激光发射器两两之间产生激光束将平面分为若干区域。 问至少删去多少个发射器可以使得原点与外侧区域联通。 多组数据数据范围 n ≤ 1 0 6 n\le10^6 n≤106 ∑ n ≤ 1 0 6 \sum n\le10^6 ∑n≤106 Solution \textit{Solution} Solution
前置知识
叉积极角排序化环为链双指针
具体解法
将发射器围成的环化环为链将发射器进行极角排序使用双指针算法找最小删除量每次得到两个指针就更新答案
瓶颈在于极角排序达到 O ( n log n ) O(n\log n) O(nlogn) 的复杂度能通过本题。
注意化环为链时开两倍数组 AC code
洛谷评测机 712 m s / 808.00 K B 712ms/808.00KB 712ms/808.00KB
核心代码
if (n3){//特判若n3易证明不需要删除cout0\n;continue;
}
sort(a1,an1);//极角排序
for (int i1;in;i)//化环为链a[in]a[i];
for (int i1,cnt1;in;i){//双指针while (cnt1nis(a[i],a[cnt1])0)cnt;ansmin({ans,cnt-i1,n-cnti-1});//更新答案
}
