首页 > 代码库 > 51nod 1278 相离的圆(排序+修改步长)

51nod 1278 相离的圆(排序+修改步长)

题目意思:

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1278

平面上有N个圆,他们的圆心都在X轴上,给出所有圆的圆心和半径,求有多少对圆是相离的。
例如:4个圆分别位于1, 2, 3, 4的位置,半径分别为1, 1, 2, 1,那么{1, 2}, {1, 3} {2, 3} {2, 4} {3, 4}这5对都有交点,只有{1, 4}是相离的。
Input
第1行:一个数N,表示圆的数量(1 <= N <= 50000)
第2 - N + 1行:每行2个数P, R中间用空格分隔,P表示圆心的位置,R表示圆的半径(1 <= P, R <= 10^9)
Output
输出共有多少对相离的圆。
Input 示例
4
1 1
2 1
3 2
4 1
Output 示例
1

题目分析:

/**
 *方法一
 *将圆分为左右短点,用线段表示,现在就变形为了线段相交问题
 *左端点left=c-r,右端点right=c+r,按左端点升序排序,相等的话
 按右端点升序排序,然或进行扫描,对于每一条线段i,当以后的某一条
 *线段j的左端点大于i的右端点,则以后的所有线段与其(i)相离
 *时间复杂度为O(nlog(n)+n^2)
 *此题的数据是50000,正常的O(n*n)的时间肯定会超时
 *现在我们可以考虑改变步长的方法优化算法(只能降低系数,但有时确实很好),
 *我在查询的时候优化,另步长为100,如果当前的j满足条件,则最先满足
 *条件的j一定在j之前的100个以内,只需要在查询j的前100个即可,
 *时间复杂度O(n*log(n)+n*(n/100+100));对于本题将你n^2的系数降低了尽100倍
 *************************************************************************
 *方法二 感谢Dava
 *把所有圆的起点和终点放在一个数组中,按大小排序(圆的左右短点表示)
 *如果某个圆的起点与另一个圆终点大小相等,则把起点排在前面
 *定义结构体
 *struct{
 *  long long d;//线段的节点
 *  int tmp;//标记起点(0)和终点(1),
 *}
 *记录所有的起点和终点直接快排,
 *令num=圆的个数,遇到起点num--,遇到终点sum+=num
 */

AC代码,方法1

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
struct node{
    int left,right;
};
node p[50005];
int cmp(node a,node b){
    if(a.left<b.left) return 1;
    else if(a.left==b.left&&a.right<b.right) return 1;
    return 0;
}
int main()
{
    int c,r,n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>c>>r;
            p[i].left=c-r;
            p[i].right=c+r;
        }
        sort(p,p+n,cmp);
        int i,j,sum=0,k;
        for(i=0;i<n;i++){
            for(j=i+100;j<n;j+=100){//步长为100
                if(p[j].left>p[i].right) break;
            }
            if(j>n) j=n;
            for(k=j-1;k>0&&k>j-101;k--){//扫描之间100个元素
                if(p[k].left<=p[i].right){
                    sum+=n-(k+1); break;
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

AC代码,方法二

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    long long d;//线段的节点
    int flag;//标记起点(0)和终点(1),
}p[100005];
int cmp(node a,node b){
    if(a.d<b.d) return 1;
    else if(a.d==b.d&&a.flag==0) return 1;
    return 0;
}
int main()
{
    int c,r,n;
    while(cin>>n){
        int k=0;
        for(int i=0;i<n;i++){
            cin>>c>>r;
            p[k].d=c-r;
            p[k++].flag=0;//起点
            p[k].d=c+r;
            p[k++].flag=1;//终点
        }
        //cout<<k<<endl;
        sort(p,p+k,cmp);
        int sum=0,num=n;
        for(int i=0;i<k;i++){
            //cout<<p[i].d<<" "<<p[i].flag<<endl;
            if(p[i].flag==0) num--;
            else if(p[i].flag==1) sum+=num;
        }
        cout<<sum<<endl;
    }
    return 0;
}



51nod 1278 相离的圆(排序+修改步长)