暑期集训积分赛（二） D. Points in rectangle

56 阅读 0 评论 37 点赞

我是靠谱客的博主温暖老师，最近开发中收集的这篇文章主要介绍暑期集训积分赛（二） D. Points in rectangle，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

暑期集训积分赛（二） D. Points in rectangle
题目：
在二维平面中有一个矩形，它的四个坐标点分别为(0,a),(a,0),(n,n−a),(n−a,n)。你现在有m个点，现在你想知道有多少个点是在这个矩形内的(边上的也算)。
输入格式：
第一行输入n,a(1≤a<n≤103)。
第二行一个正整数m(1≤m≤103),代表你拥有的点的个数，接下来m行，每行一个点的坐标xi,yi(1≤xi,yi≤103)
输出格式：
第一行输出在矩形内的点的个数，然后输出在矩形内点的坐标，横坐标大的优先，如果横坐标相同，则纵坐标大的优先。如果没有，输出−1。
input:
6 1
5
1 2
1 3
2 3
3 4
4 5
output:
4
4 5
3 4
2 3
1 2
//用优先队列
代码+解释：

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
struct node
{
	double x;
	double y;//记录坐标对 
	/*bool operator<(const node & p)const//此行<符号不能改变  A
	{  
		if(x==p.x)
			return y<p.y;//如果横坐标相同 ，则按纵坐标降序排列
		else
			return x<p.x;//按横坐标降序排列
	}*/
	bool operator<(const node & p)const//此行<符号不能改变  B
	{  
		if(x==p.x)
			return y>p.y;//如果横坐标相同 ，则按纵坐标升序排列
		else
			return x>p.x;//按横坐标升序排列
	}
	/*bool friend operator<(node a,node b)//此行<符号不能改变  C
	{
		if(a.x==b.x)
			return a.y<b.y;//如果横坐标相同 ，则按纵坐标降序排列
		else
			return a.x<b.y;//按横坐标降序排列 
	}*/
	/*bool friend operator<(node a,node b)//此行<符号不能改变  D
	{
		if(a.x==b.x)
			return a.y>b.y;//如果横坐标相同 ，则按纵坐标升序排列
		else
			return a.x>b.y;//按横坐标升序排列 
	}*/
	//以上两种重载形式均可 
};
//6 1 6 1 2 1 3 2 3 3 4 4 5 4 4.5
int main()
{
	double n,a;
	int m;
	double x,y;
	priority_queue<node>que;//定义一个优先队列
	while(cin>>n>>a>>m)
	{
		int count=0; 
		for(int i=0;i<m;i++)//一共有点m个，循环m次
		{
			node p;//定义一个结构体 
			cin>>x>>y;
			p.x=x;
			p.y=y;//存入 
			if(y<=x+a && y>=x-a && y<=2*n-a-x && y>=a-x)//判定是否在矩形
			{
				count++;//每满足一个数次数就加一 
				que.push(p);//如果坐标满足条件，就把坐标放进队列 
			}
		}
		//把所有的坐标对存入结构体放进队列之后
		if(count==0)
			cout<<"-1"<<endl;
		else
		{
			cout<<count<<endl;
			for(int i=0;i<count;i++)
			{
				node q=que.top();
				cout<<q.x<<" "<<q.y<<endl;
				que.pop();//清空 
				//在队列输出过程中，以运行B为例
				//测试数据：
				//6 1 
				//6 
				//1 2 
				//1 3 
				//2 3 
				//3 4 
				//4 5 
				//4 4.5
				//输出：
				//5
				//1 2
				//3 4
				//2 3
				//4 4.5
				//4 5 
				//if(x==p.x)
				//	return y>p.y;//如果横坐标相同 ，则按纵坐标升序排列，当横坐标相同时纵坐标越小的先出列 
				//else
				//	return x>p.x;//按横坐标升序排列，说明横坐标越小先出列 
			}	
		}
		
	}
	return 0;
}