社区讨论
70分求调
P1158[NOIP 2010 普及组] 导弹拦截参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @m3u1gfqo
- 此快照首次捕获于
- 2024/11/23 18:39 去年
- 此快照最后确认于
- 2025/11/04 14:05 4 个月前
本人做法是先找到一个圆,然后再找第二个:先判断每个点距离哪个初始点比较近,把它归类为属于这个初始点的点,然后找到长度^(2)最大的点,它与它的归属点相连是这个圆的半径,然后再判断另一个圆,但是70分,求调;谢谢大佬
C#include <stdio.h>
#include <math.h>
int val_cal(int x,int y,int xn,int yn){
return (x-xn) * (x-xn) + (y-yn) * (y-yn);
}
struct point{
int x,y;
int belong;
}a[100005];//belong 表示这个点距离哪个初始点比较近,叫做属于点1 或2
int main(){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int n,max1 = 0,max2 = 0,key;//max1表示属于1的点里面距离点1最远的点长度^2;max2同理
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
int l1 = val_cal(a[i].x,a[i].y,x1,y1);
int l2 = val_cal(a[i].x,a[i].y,x2,y2);//分别计算,比较这个点距离哪个初始点比较近
if(l1 <= l2){//到点1比较近
a[i].belong = 1;
if (l1 > max1) max1 = l1;
}
else {//到2
a[i].belong = 2;
if(l2 > max2) max2 = l2;
}
}
int lmax;
if(max1 >= max2){//最远的点是属于1的,那么所有属于1的点就不必讨论了,只需要去看一遍所有属于2的点有没有在1的圆内
key = 1;
lmax = max1;
}
else {//最远的点是属于2的
key = 2;
lmax = max2;
}
int rmax = 0;//rmax表示另一个初始点展开的大小
for(int i=1;i<=n;i++){
if( a[i].belong == key){
continue;//如果属于之前画过的圆,就不讨论了,肯定被包含
}
if(key == 1 && val_cal(a[i].x,a[i].y,x1,y1)>lmax){//如果之前的圆是初始点1展开的,但是无法包含讨论点
rmax = fmax(rmax , val_cal(a[i].x,a[i].y,x2,y2));
// printf("i = %d %d\n",i, rmax);
continue;
}
else if(key == 2 && val_cal(a[i].x,a[i].y,x2,y2)>lmax){//如果之前的圆是初始点2展开的,但是无法包含讨论点
rmax = fmax(rmax , val_cal(a[i].x,a[i].y,x1,y1));
// printf("%d\n",rmax);
}
}
printf("%lld",(long long) (lmax + rmax));
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...