社区讨论

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 条回复,欢迎继续交流。

正在加载回复...