The 46th ICPC EC Regional Macau Nowcoder 31454C Laser Trap 极角排序
Nowcoder 31454C Laser Trap

题意:二维平面上有n个激光发射器,在两两之间产生激光束,你不能穿过激光发射器和激光束,求要从(0,0)出发走到无穷远至少需要移除的激光发射器数目

考虑在原点处建立极坐标系,两个激光发射器的阻拦范围就是原点向它们连线所夹的劣角,因此,能走到无限远当且仅当全部激光发射器能被同一个劣角包含。

我们先对发射器的坐标进行极角排序,保证发射器的极角递增,然后顺次枚举发射器,对每个发射器,我们找到能与它组成劣角且离它最远的发射器,这个劣角之内的全部发射器都可以保留,而在这个劣角之外的其它发射器就是要达成题目条件所必须移除的。不断用以当前发射器为始可以保留的发射器数目更新可以保留的发射器数目的最大值,用发射器总数减去则得到移除发射器数目的最小值(或者直接用必须移除的发射器数目更新移除发射器数目的最小值)就可以得到答案。特别的,如果”能与它组成劣角且离它最远的发射器”是它本身,则说明没有发射器可以保留。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template <typename T> inline T read(){
	T sum = 0;
	int fl = 1,ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
	for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

constexpr int maxn = 1e6 + 5;

int T;
int n;

struct line{//一般式,Ax + By = C
	double A;
	double B;
	double C;
};

struct point{//二维点,数据类型要看题目确定
	LL x;
	LL y;
    point () {}
    point (LL a, LL b) {x = a, y = b;}
    bool up () const {//判断点是否在x轴上方(极角排序用的,因为叉积不是偏序关系,只有在x轴同一侧才能用叉积比较极角)
        return y > 0 || (y == 0 && x >= 0);
    }
}a[maxn];

LL det(point x,point y){//叉乘
    return x.x * y.y - y.x * x.y;
}

LL dot(point x,point y){//点乘
    return x.x * y.x + x.y * y.y;
}

bool cmp (point a, point b) {//极角排序的cmp()
    if (a.up() ^ b.up()) return a.up() > b.up();//如果两点不在x轴的同一侧,x轴上方的点对应极角一定比x轴下方的点小
    return det(a, b) > 0;//以极角升序排序,a的极角小于b的极角时det(a,b) > 0
}

bool check(point a,point b){//判断ab逆时针夹角是劣角还是优角(也就是夹角是正的还是负的)
	LL d = det(a,b);
	if(d > 0) return true;
	if(d < 0) return false;
	return dot(a,b) > 0;
}

void Solve(){
	n = read<int>();
	for(int i = 1; i <= n; i++){
		a[i].x = read<LL>();
		a[i].y = read<LL>();
	}
	sort(a + 1,a + n + 1,cmp);
	LL ans = n;
	for(int i = 1,j = 1; i <= n; i++){
		while(check(a[i],a[j])){
			if(++j > n) j = 1;
			if(j == i){//如果j能走到i说明其它所有点与它的夹角能被同一劣角包含,从另一边走掉就可以
				puts("0");
				return;
			}
		}
		ans = min(ans,n - ((LL)(j - i + n) % n));
	}
	printf("%lld\n",ans);
}

int main(){
	T = read<int>();
	while(T--) Solve();
	return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇