蓝桥杯2015年第六届真题-广场舞-题解(C++代码)

1057 阅读 5 评论 0 点赞

原题链接：蓝桥杯2015年第六届真题-广场舞

#### 原题链接：[问题 1838: [蓝桥杯][2015年第六届真题]广场舞](https://www.dotcpp.com/oj/problem1838.html "问题 1838: [蓝桥杯][2015年第六届真题]广场舞")

写了好多的基础题，应该适当的做一些提高了，看了一个多小时只有思路不够清晰，也查阅了一些资料和大佬的代码，自己不断去理解才完美ac

#### 解题思路：
**1、先找到所有的点 最大的横纵点和最小的横纵点，然后判断范围内的其他三个点是否在这个多边形中
2、每判断一次如果符合条件就计数加一，如不符合就重新遍历**

![](/image_editor_upload/20190824083145_55204.png)

#### 代码如下：
```cpp
#include<iostream>
using namespace std;
int sum_1=0,n;
int max(int a,int b){
    if(a>b)
        return a;
        else 
        return b;
}
int min(int a,int b){
    if(a>b)
        return b;
        else 
        return a;
}
bool demo_point(int point[][2],int x,int y)
{
	bool flag=false;
	int i=0,j=n-1;
	for(;i<n;i++)//遍历每一个坐标
	{
		if(min(point[i][1],point[j][1])<y&&max(point[i][1],point[j][1])>=y)//得到纵坐标最小值并且纵坐标最大值 
		{
			double t=(double)point[i][0]+(double)(((double)(y-point[i][1])/(double)(point[i][1]-point[j][1]))*((double)(point[i][0]-point[j][0])));
			//求斜率 
			if(t<x)
	{
		flag=!flag;
	}
	}
	j=i;
	}
	return flag;
}
int main()
{
	int i;
	int point[100][2];
	int max_x=-100000,max_y=-100000;
	int min_x=100000,min_y=100000; 
	cin>>n;
	for(i=0;i<n;i++)
	{
		 	cin>>point[i][0]>>point[i][1];
            if(point[i][0]>max_x)    max_x=point[i][0];  
            if(point[i][0]<min_x)    min_x=point[i][0];  
            if(point[i][1]>max_y)    max_y=point[i][1];  
            if(point[i][1]<min_y)    min_y=point[i][1];
	}
	for(i=min_x;i<max_x;i++){  //x从最小到最大 
            for(int j=min_y;j<max_y;j++){  //y从最小到最大 
                if(demo_point(point,i,j)&&demo_point(point,i+1,j)&&demo_point(point,i,j+1)&&demo_point(point,i+1,j+1)){  //其他三个点是否构成一个方格且满足范围 
                    sum_1++;  
                }  
            }  
        }  
        cout<<sum_1<<endl;
	return 0;
 }

```

**由于作者能力有限，那里如果有不对的地方，衷心希望广大网友批评指正。
有问题可以留言哟。**

0.0分

7 人评分

本文分类：题解列表
浏览次数：1057 次浏览
发布日期：2019-08-24 21:13:44
本文链接：https://blog.dotcpp.com/a/61475

上一篇 > 蓝桥杯2017年第八届真题-k倍区间（C++代码）前缀和O(n)算法
下一篇 > 数据结构-行编辑程序-题解(C语言代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

蓝桥杯2015年第六届真题-广场舞-题解(C++代码)

评论列表共有 5 条评论

发表评论取消回复

蓝桥杯2015年第六届真题-广场舞-题解(C++代码)

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 5 条评论

发表评论 取消回复

评论列表共有 5 条评论

发表评论取消回复