网站改版换域名,wordpress ajax 登陆,wordpress服务器要多大内存,电商设计师联盟网站广场舞LQ市的市民广场是一个多边形#xff0c;广场上铺满了大理石的地板砖。
地板砖铺得方方正正#xff0c;就像坐标轴纸一样。
以某四块砖相接的点为原点#xff0c;地板砖的两条边为两个正方向#xff0c;一块砖的边长为横纵坐标的单位长度#xff0c;则所有横纵坐标都…广场舞LQ市的市民广场是一个多边形广场上铺满了大理石的地板砖。
地板砖铺得方方正正就像坐标轴纸一样。
以某四块砖相接的点为原点地板砖的两条边为两个正方向一块砖的边长为横纵坐标的单位长度则所有横纵坐标都为整数的点都是四块砖的交点如果在广场内。
广场的砖单调无趣却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚都会有大批市民前来跳舞。
舞者每次都会选一块完整的砖来跳舞两个人不会选择同一块砖如果一块砖在广场边上导致缺角或者边不完整则没人会选这块砖。
广场形状的例子参考【图1.png】现在告诉你广场的形状请帮LQ市的市长计算一下同一时刻最多有多少市民可以在广场跳舞。【输入格式】
输入的第一行包含一个整数n表示广场是n边形的因此有n个顶点。
接下来n行每行两个整数依次表示n边形每个顶点的坐标也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。
【输出格式】
输出一个整数表示最多有多少市民可以在广场跳舞。【样例输入】
5
3 3
6 4
4 1
1 -10 4【样例输出】
7【样例说明】广场如图1.png所示一共有7块完整的地板砖因此最多能有7位市民一起跳舞。【数据规模与约定】
对于30%的数据n不超过100横纵坐标的绝对值均不超过100。
对于50%的数据n不超过1000横纵坐标的绝对值均不超过1000。
对于100%的数据n不超过1000横纵坐标的绝对值均不超过100000000一亿。资源约定
峰值内存消耗 256M
CPU消耗 1000ms
请严格按要求输出不要画蛇添足地打印类似“请您输入...” 的多余内容。
所有代码放在同一个源文件中调试通过后拷贝提交该源码。
注意不要使用package语句。不要使用jdk1.7及以上版本的特性。注意主类的名字必须是Main否则按无效代码处理。
思路有ACM经验的大牛一定一眼就能看出来这是个凸包问题当然人家都不会看这种水平的题......好了言归正传想深入了解凸包问题的可以参考下面两篇文章。
蛮力法在求解凸包问题中的应用JAVA
分治法在求解凸包问题中的应用JAVA--快包算法
单就这个题目还达不到传统凸包问题的难度所以不了解也可以做。我们只需要判断在所围面积中的点它的右侧、下侧、右下侧三个点是否也在范围内就可以了。如果都在范围内那么这个砖就是完整的反之不是完整的。
以下图为例我们可能不能漫无边际的处理任意个点所以我们可以先找出所有坐标中的x的上下限y的上下限即图中红色虚线所围区域。之后对区域中的每个点进行判断。而如何判断一个点是不是在所围区域之内呢这里需要用到两点式直线方程的概念我们构成边界的点x1,y1(x2,y2)两两带入两点式再带入所判断点(x,y)的一个坐标dy就可以求出另一个坐标dx。而求出来的坐标dx如果在实际x的左侧则不再范围内反之在范围内。完整代码如下
public class Point {int x;int y;public Point(int x, int y) {// TODO Auto-generated constructor stubthis.x x;this.y y;}
}import java.util.Scanner;public class Main {static int cnt 0;public static void main(String[] args) {Scanner in new Scanner(System.in);int n in.nextInt();Point[] points new Point[n];int maxX 0, minX 99999999;int maxY 0, minY 99999999;for(int i 0; i n; i) {int x in.nextInt();int y in.nextInt();points[i] new Point(x, y);if(points[i].x maxX) {maxX points[i].x;}if(points[i].x minX) {minX points[i].x;}if(points[i].y maxY) {maxY points[i].y;}if(points[i].y minY) {minY points[i].y;}}for(int i minX; i maxX; i) { //x的最小值到最大值for(int j minY; j maxY; j) { //y的最小值到最大值//判读右、下、右下的三个点是否都在范围内if(f(points, i, j) f(points, i1, j) f(points, i, j1) f(points, i1, j1)) {cnt;}}}System.out.println(cnt);}public static boolean f(Point[] points, int x, int y) {boolean flag false;/*** 由于输入时按顺序的所以计算还简单了只需要求出0点-1点、1点-2点、2点-3点、3点-4点、(4点-0点)的斜率即可。* 其中4点-0点不好求这里的做法非常巧妙首先将j赋为4先将4点和0点比较之后 ji,i ,避免了双层嵌套还解决了回环的问题。* */int j points.length - 1;for(int i 0; i points.length; i) {// 各点y坐标值的最小值 y坐标值的最大值if(y Math.min(points[i].y, points[j].y) y Math.max(points[i].y, points[j].y)) {//两点式获得斜率确定该点是否在范围内double temp (double) points[i].x (double)((( y- points[i].y)/ (double)(points[i].y - points[j].y)) * (double)((points[i].x - points[j].x)));if(temp x) {flag true;}}j i;}return flag;}
}
