灯塔 pro (LightHouse pro)

描述

海上有许多灯塔,为过路船只照明。

(图一)

如图一所示,每个灯塔都配有一盏探照灯,照亮其东北、西南两个对顶的直角区域。探照灯的功率之大,足以覆盖任何距离。灯塔本身是如此之小,可以假定它们不会彼此遮挡。

(图二)

如图二所示,给定一片矩形的海域,有部分灯塔可以完全照亮它,有一部分灯塔则不行。比如对于图中虚线部分表示的矩形,它可以被灯塔R照亮,却不能被灯塔G和灯塔B照亮。

现在,已知海域中所有灯塔的坐标,我们希望查询给定的矩形区域可以被多少个灯塔照亮。

 

 

输入

共2+n+k行。

第1行为1个整数n,表示灯塔的总数。

接下来的n行每行包含2个整数x, y,分别表示各灯塔的横、纵坐标。

第n+2行为1个整数k,表示查询的次数

接下来的k行每行包含四个整数x1, y1, x2, y2,表示所查询矩形的左下、右上顶点的坐标

 

 

输出

共k行,依次为各次查询中能照亮该矩形区域的灯塔数量

 

 

输入样例

5

1 1

2 2

4 3

5 1

100 100

2

1 1 10 10

1 1 200 200

 

 

输出样例

2

1

 

 

限制

0 <= n <= 100,000

0 <= k <= 100,000

灯塔的坐标以及查询的坐标是[0, 10,000,000]内的整数

时间:2s,内存:256MB

 

 

 

 

   我的基本思路是先把数据按x快速排序,然后用二分搜索不小于x2的数据的范围,将此范围内的数据按y快速排序,然后二分搜索不小于y2的范围,根据此范围大小即可算出在所求矩形右上的灯塔数目,然后将范围内的数据按x快排回来就行~;左下的灯塔数目同理,只需将不小于改为不大于即可~~

 

#include

using namespace std;

struct position
{
   long long x,y;
}pos[10000001];

template
void Swap(T *a,T *b)
{
   T temp=*a;
   *a=*b;*b=temp;
}

void QSortX(position A[],long long left,long long right)    //快速排序
{
   long long i,j;
   if(left        i=left,j=right+1;
       Swap(&A[left],&A[(left+right)/2]);  //把中间元素与第一个元素交换,即可实现以中间元素为关键字或分割元素,排列
       do{
           do i++;while(A[i].x            do j–;while(A[j].x>A[left].x);
           if(i        }while(i        Swap(&A[left],&A[j]);//std::cout<<"   "<        //std::cout<        QSortX(A,left,j-1);
       //std::cout<        QSortX(A,j+1,right);
   }
}

void QSortY(position A[],long long left,long long right)    //快速排序
{
   long long i,j;
   if(left        i=left,j=right+1;
       Swap(&A[left],&A[(left+right)/2]);  //把中间元素与第一个元素交换,即可实现以中间元素为关键字或分割元素,排列
       do{
           do i++;while(A[i].y            do j–;while(A[j].y>A[left].y);
           if(i        }while(i        Swap(&A[left],&A[j]);//std::cout<<"   "<        //std::cout<        QSortY(A,left,j-1);
       //std::cout<        QSortY(A,j+1,right);
   }
}

long long BinSearchMinX(position A[],long long left,long long right,long long x)    //查找不小于
{
   long long middle;
   while(left <= right)
   {
       middle=(left+right)/2;
       if(x==A[middle].x)
       {
           return middle;
       }
       else if(x>A[middle].x)
           {
               left=middle+1;
           }
           else
           {
               right=middle-1;
           }
   }//循环退出条件:start > end 没有找到x,返回小于x的最大元素位置LEFT和大于x的最小元素位置RIGHT
   if(left>middle) return middle+1;
   else return middle;
}

long long BinSearchMinY(position A[],long long left,long long right,long long y)    //查找不小于
{
   long long middle;
   while(left <= right)
   {
       middle=(left+right)/2;
       if(y==A[middle].y)
       {
           return middle;
       }
       else if(y>A[middle].y)
           {
               left=middle+1;
           }
           else
           {
               right=middle-1;
           }
   }//循环退出条件:start > end 没有找到x,返回小于x的最大元素位置LEFT和大于x的最小元素位置RIGHT
   if(left>middle) return middle+1;
   else return middle;
}

////////////////////////////////////////////////

long long BinSearchMaxX(position A[],long long left,long long right,long long x)    //查找不大于
{
   long long middle;
   while(left <= right)
   {
       middle=(left+right)/2;
       if(x==A[middle].x)
       {
           return middle;
       }
       else if(x>A[middle].x)
           {
               left=middle+1;
           }
           else
           {
               right=middle-1;
           }
   }//循环退出条件:start > end 没有找到x,返回小于x的最大元素位置LEFT和大于x的最小元素位置RIGHT
   if(left>middle) return middle;
   else return middle-1;
}

long long BinSearchMaxY(position A[],long long left,long long right,long long y)    //查找不大于
{
   long long middle;
   while(left <= right)
   {
       middle=(left+right)/2;
       if(y==A[middle].y)
       {
           return middle;
       }
       else if(y>A[middle].y)
           {
               left=middle+1;
           }
           else
           {
               right=middle-1;
           }
   }//循环退出条件:start > end 没有找到x,返回小于x的最大元素位置LEFT和大于x的最小元素位置RIGHT
   if(left>middle) return middle;
   else return middle-1;
}

 

int main()
{
   long long n,i;
   cin>>n;
   for(i=0;i    {
       cin>>pos[i].x>>pos[i].y;
   }
   QSortX(pos,0,n-1);

   long long k,x1,y1,x2,y2,t1,t2,count;
   cin>>k;
   for(i=0;i    {
       count=0;
       cin>>x1>>y1>>x2>>y2;

       //查找不小于x2的
       t1=BinSearchMinX(pos,0,n-1,x2);
       QSortY(pos,t1,n-1);
       t2=BinSearchMinY(pos,t1,n-1,y2);
       QSortX(pos,t1,n-1);

       count=n-t2;//cout<

       //查找不大于x1的
       t1=BinSearchMaxX(pos,0,n-1,x1);
       QSortY(pos,0,t1);
       t2=BinSearchMaxY(pos,0,t1,y1);
       QSortX(pos,0,t1);

       count=count+t2+1;

       cout<

   }

   return 0;
}

 

 

但提交清华OJ后,只跑出两组正确,剩下18组全是Runtime error (exitcode: 11),这是为毛线啊?百度说是有访问的数组越界,但我检查了两遍也都没有呀~~有大神能看看的吗?

灯塔 pro (LightHouse pro)》上有1条评论

  1. Pingback引用通告: BZ编程小组 作品 | BZ编程小组

发表评论

电子邮件地址不会被公开。 必填项已用*标注