Problem 4027 --星球大战

4027: 星球大战

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

2035年 X星人入侵,地球在经过前期惨烈的战争后,研究出了一门射线武器,并打算在最终的决战。但是在大战中,要避免伤害到友军的战舰。

可以假设战场是一个二维的坐标系,射线武器安装在(0,0)的位置,可以从一个方向射出射线,并消灭在与射线相交的所有战舰。给出每艘战舰的舰首和舰尾的坐标(为整数)。请你计算出最少需要多少次射击可以在不击中友军的情况下,消灭所有敌军

第一行为 N和M,分别代表友军和敌军的数目,0 <= N,M<= 10^5。

接下来N+M行,每行四个整数 x1,y1,x2,y2 用一条线段,(x1,y1) (x2,y2) 来描述一艘战舰的位置。前N行描述的是敌军,后M行描述的是友军。-1000 <= x1,x2,y1,y2 <= 1000,表示战舰的线段之间可能相交,战舰也可经过原点,则任何的射击都会被消灭。

可以消灭所有敌军而不伤到友军的情况,输出最少射击次数。否则,输出No solution
4 4
2 4 4 0
-2 6 -2 -2
-4 2 4 -2
-6 8 -2 -4
4 6 -4 4
6 0 2 -4
-8 4 -8 0
4 4 6 2
2

推荐代码 查看4027 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$5 $ms] 多人运动小组 962587 2023-05-11 18:28:22
内存最少[$6992 $KB] 多人运动小组 962587 2023-05-11 18:28:22
第一AC 多人运动小组 962587 2023-05-11 18:28:22
第一挑战 多人运动小组 962586 2023-05-11 18:26:52

赛题来源/所属竞赛 安徽省机器人大赛2022年本科组 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛