Tag Archives: 几何

hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

#1552 : 缺失的拼图

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi在玩一个拼图游戏。如下图所示,整个拼图是由N块小矩形组成的大矩形。现在小Hi发现其中一块小矩形不见了。给定大矩形以及N-1个小矩形的顶点坐标,你能找出缺失的那块小矩形的顶点坐标吗?

输入

第一行包含一个整数,N。
第二行包含四个整数,(X0, Y0), (X'0, Y'0),代表大矩形左下角和右上角的坐标。
以下N-1行每行包含四个整数,(Xi, Yi), (X'i, Y'i),代表其中一个小矩形的左下角和右上角坐标。
对于30%的数据, 1 <= N <= 1000
对于100%的数据,1 <= N <= 100000 所有的坐标(X, Y)满足 0 <= X, Y <= 100000000

输出

输出四个整数(X, Y), (X', Y')代表缺失的那块小矩形的左下角和右上角的坐标。

样例输入
5
0 0 4 5
0 0 3 1
0 1 2 5
3 0 4 5
2 2 3 5
样例输出
2 1 3 2

一个矩形由N个小矩形拼接而成,现在丢了一个小矩形,怎样才能找到这个小矩形呢。所有矩形都用左下角坐标和右上角坐标表示。
这一题也很有意思,丢掉的那个小矩形的坐标肯定是其他N-1个矩形的坐标中的某4个。我们可以统计每个坐标点出现的次数,如果出现偶数次,则这个点所在的矩形是出现过的,否则这个点就是缺失矩形的某个顶点。最后,从缺失的4个顶点中找出左下角坐标和右上角坐标。
完整代码如下:

#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> Point;
int main() {
	//freopen("input.txt", "r", stdin);
	int n;
	scanf("%d", &n);
	map<Point, int> hash;
	int a, b, c, d;
	while (n--) {
		Point left_bottom, right_top;
		scanf("%d %d %d %d", &left_bottom.first, &left_bottom.second, &right_top.first, &right_top.second);
		Point left_top = Point(left_bottom.first, right_top.second), right_bottom = Point(right_top.first, left_bottom.second);
		++hash[left_bottom];
		++hash[right_top];
		++hash[left_top];
		++hash[right_bottom];
	}
	set<Point> ans;
	for (auto p : hash) {
		if (p.second % 2 == 1) {
			ans.insert(p.first);
		}
	}
	a = c = ans.begin()->first;
	b = d = ans.begin()->second;
	for (auto p : ans) {
		a = min(a, p.first);
		b = min(b, p.second);
		c = max(c, p.first);
		d = max(d, p.second);
	}
	printf("%d %d %d %d\n", a, b, c, d);
	return 0;
}

本代码提交AC,用时432MS。

LeetCode Valid Triangle Number

LeetCode Valid Triangle Number
Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

  1. The length of the given array won't exceed 1000.
  2. The integers in the given array are in the range of [0, 1000].

给定一个数组,问从中能取出所少个三元数组,使得取出的三个数能构成一个三角形。
首先明确三条线段构成三角形的条件是任意两边之和要大于第三遍。
先上暴力,直接dfs枚举出所有的三元组,判断能构成三角形,则方案数加1。代码如下:

class Solution {
private:
	void dfs(int &ans, vector<int>& nums, vector<int>& cand, int idx) {
		if (cand.size() == 3) {
			int &a = cand[0], &b = cand[1], &c = cand[2];
			if (a + b > c&&a + c > b&&b + c > a) {
				++ans;
				//cout << a << "\t" << b << "\t" << c << endl;
			}
			return;
		}
		for (int i = idx; i < nums.size(); ++i) {
			if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
			cand.push_back(nums[i]);
			dfs(ans, nums, cand, i + 1);
			cand.pop_back();
		}
	}
public:
	int triangleNumber(vector<int>& nums) {
		int ans = 0;
		vector<int> cand;
		sort(nums.begin(), nums.end());
		dfs(ans, nums, cand, 0);
		return ans;
	}
};

本代码提交TLE:219 / 243。数组最大长度是1000,则所有的组合数有1000*999*998=997002000,确实有点大。。。
后来我发现,报TLE的大数据,虽然有1000个数,但是有很多都是重复的,真正不同的数大概只有100个左右。所以我就想,先对数据去重,在所有互异的数中dfs。然后根据每条边重复的次数来求组合数。
比如样例中,互异的数是[2,3,4],dfs发现[2,3,4]可以构成三角形,则所有由[2,3,4]构成的三角形的个数应该是count[2]*count[3]*count[4]=2*1*1=2。
所以我们先对数组做个hash,统计数值及其出现频率的关系。注意,因为边的长度最大也只为1000,所以用一个1000长的数组来hash比用map或者unordered_map占用的内存更少,否则会MLE。
然后分三类情况进行计算:1. 三条边互不相同;2.有两条边的值相等;3.三条边的值都相等。
其中第一种情况用常规的DFS求解。第二种和第三种情况就是简单的枚举。
还需要注意一点是,边长为0的值需要过滤掉。
完整代码如下:

class Solution {
private:
	void dfs(int& ans, vector<int>& count, vector<int>& nums, vector<int>& cand, int idx) {
		if (cand.size() == 3) {
			int &a = cand[0], &b = cand[1], &c = cand[2];
			if (a + b > c&&a + c > b&&b + c > a) {
				ans += count[a] * count[b] * count; // 三边各异
				//cout << a << "\t" << b << "\t" << c << endl;
			}
			return;
		}
		for (int i = idx; i < nums.size(); ++i) {
			if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
			cand.push_back(nums[i]);
			dfs(ans, count, nums, cand, i + 1);
			cand.pop_back();
		}
	}
public:
	int triangleNumber(vector<int>& nums) {
		vector<int> mii(1001, 0);
		for (const auto& i : nums)++mii[i]; // hash
		vector<int> distinct;
		for (int i = 1; i < 1001; ++i) {
			if (mii[i] > 0)distinct.push_back(i);
		}
		int ans = 0;
		vector<int> cand;
		dfs(ans, mii, distinct, cand, 0); // 三边互不相同
		int n = distinct.size();
		for (int i = 0; i < n; ++i) {
			if (mii[distinct[i]] >= 3) { // 三边相同
				int &d = mii[distinct[i]];
				ans += (d*(d - 1)*(d - 2)) / 6;
			}
			for (int j = i + 1; j < n; ++j) {
				if (mii[distinct[i]] >= 2) { // 两条边一样
					int &a = distinct[i], &b = distinct[i], &c = distinct[j];
					if (a + b > c&&a + c > b&&b + c > a) {
						ans += (mii[a] * (mii[a] - 1) / 2)*mii;
					}
				}
				if (mii[distinct[j]] >= 2) { // 两条边一样
					int &a = distinct[i], &b = distinct[j], &c = distinct[j];
					if (a + b > c&&a + c > b&&b + c > a) {
						ans += (mii[b] * (mii[b] - 1) / 2)*mii[a];
					}
				}
			}
		}
		return ans;
	}
};

本代码提交AC,用时1589MS。

LeetCode Valid Square

LeetCode Valid Square
Given the coordinates of four points in 2D space, return whether the four points could construct a square.
The coordinate (x,y) of a point is represented by an integer array with two integers.
Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True

Note:

  1. All the input integers are in the range [-10000, 10000].
  2. A valid square has four equal sides with positive length and four equal angles (90-degree angles).
  3. Input points have no order.

任给平面上的四个点,问这四个点能否构成正方形。
解法1,原始几何角度。
如果要构成正方形,必须满足四条边相等,且四个角是直角。因为给定的点的顺序是不固定的,假设我们固定一个点p1,求p1到其他三个点p2,p3,p4的距离的平方len2,len3,len4,则要形成正方形,这三个距离中必定有两个距离相等,且等于另一个距离的两倍。

p3------p4
|       |
|       |
p1------p2

比如假设形成上述正方形,则有2*len2==2*len3==len4。在满足这个条件的基础上,还需要满足p1p2垂直p1p3,且p4p3垂直p4p2,且p4到p2和p3的距离相等。
当然因为点的顺序不固定,所以还有可能2*len2==2*len4==len3或者2*len3==2*len4==len2。最后需要注意的是这些点中不能由任何两个点重合,所以需要判断两点之间的距离不能为0。
完整代码如下:

class Solution2 {
private:
	// 计算距离的平方
	int distSquare(const vector<int>& p1, const vector<int>& p2) {
		return (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]);
	}
	// 判断直线(p1,p2)和直线(p3,p4)是否垂直
	bool isVertical(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
		return (p2[0] - p1[0])*(p4[0] - p3[0]) + (p2[1] - p1[1])*(p4[1] - p3[1]) == 0;
	}
	// 在2|p1p2|==2|p1p3|==|p1p4|的条件下,判断是否能形成正方形
	bool helper(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
		if (!isVertical(p1, p2, p1, p3))return false;
		if (!isVertical(p4, p3, p4, p2))return false;
		int len2 = distSquare(p4, p2), len3 = distSquare(p4, p3);
		return len2 == len3;
	}
public:
	bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
		int len2 = distSquare(p1, p2), len3 = distSquare(p1, p3), len4 = distSquare(p1, p4);
		if (len2 == 0 || len3 == 0 || len4 == 0)return false;
		if (len2 == len3 && 2 * len2 == len4) return helper(p1, p2, p3, p4);
		if (len2 == len4 && 2 * len2 == len3) return helper(p1, p2, p4, p3);
		if (len3 == len4 && 2 * len3 == len2) return helper(p1, p3, p4, p2);
		return false;
	}
};

本代码提交AC,用时6MS。
解法2,特征法。
任何一个正方形,如果求出所有点之间的距离,则这些距离只可能有两种取值,一种是邻边全相等,另一种是对角边也相等。所以我们只需要用一个map保存不同边的长度以及出现的频率即可,如果最终只有两个映射,则是正方形,否则不是。注意当出现边长为0时,说明两点重合,不能构成正方形。
代码如下:

class Solution {
private:
	// 计算距离的平方
	int distSquare(const vector<int>& p1, const vector<int>& p2) {
		return (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]);
	}
public:
	bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
		unordered_map<int, int> umdist;
		vector<vector<int>> points = { p1,p2,p3,p4 };
		for (int i = 0; i < 4; ++i) {
			for (int j = i + 1; j < 4; ++j) {
				int dist = distSquare(points[i], points[j]);
				if (dist == 0)return false;
				++umdist[dist];
			}
		}
		return umdist.size() == 2;
	}
};

本代码提交AC,用时9MS。
不过上述代码有局限性,如果顶点都只是整数,则没有问题,但是如果顶点可以是实数,则会有问题。比如等边三角形的三个点和三角形的中心点,这四个点两两之间只有2种不同的距离,但他们不能构成正方形。可以再加一个限制条件,即两种不同长度的边的频率一个是4,一个是2,且出现2次的边长是出现4次的边长的两倍。
讨论区见:https://discuss.leetcode.com/topic/89985/c-3-lines-unordered_set/4

LeetCode Rectangle Area

LeetCode Rectangle Area
Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Rectangle Area
Assume that the total area is never beyond the maximum possible value of int.

给定两个矩形,要求这两个矩形的面积和,如果有重叠区域,需要减去重叠区域的面积。因为这两个矩形的关系是rectilinear的,也就是像图中互相平行分布的,不会出现一个矩形斜着和另一个矩形相交(这样重叠区域可能是三角形或梯形)。
此题的难点是怎样判断两个矩形是否相交,肉眼很容易判断,但是怎样写一个通用程序呢。我原来的思路是先判断哪个矩形面积更小,然后判断小面积矩形是否有顶点落在大面积矩形内部,如果有则相交,否则不想交。
网上有一种比较简单的判断方法,它不判断两个矩形是否相交,而是判断两个矩形是否不相交,方法是判断一个矩形是否完全落在另一个矩形的上、下、左、右侧。因为矩形是rectilinear的,所以每侧判断只需一语句就行,比如判断图中右边那个矩形是否完全在左边矩形的右边,只需判断E>=C是否成立。
还有一种判断方法是,把两个矩形的顶点分别投影到x轴和y轴,如果投影到两个轴上的两条线段都不相交,则矩形没有重叠。
重叠之后求交集区域的面积也不难,比如上图,交集矩形x轴左端点是A,E的较大值,右端点是C,G的较小值,y轴类似。
完整代码如下:

class Solution {
public:
	int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
		int area = (C - A)*(D - B) + (G - E)*(H - F);
		if (E >= C || // 右
			H <= B || // 下
			G <= A || // 左
			F >= D) // 上
			return area;
		return area - (min(C, G) - max(A, E))*(min(D, H) - max(B, F));
	}
};

本代码提交AC,用时22MS。

hihoCoder 1040-矩形判断

hihoCoder 1040-矩形判断
#1040 : 矩形判断
时间限制:1000ms
单点时限:1000ms
内存限制:256MB
描述
给出平面上4条线段,判断这4条线段是否恰好围成一个面积大于0的矩形。
输入
输入第一行是一个整数T(1<=T<=100),代表测试数据的数量。
每组数据包含4行,每行包含4个整数x1, y1, x2, y2 (0 <= x1, y1, x2, y2 <= 100000);其中(x1, y1), (x2,y2)代表一条线段的两个端点。
输出
每组数据输出一行YES或者NO,表示输入的4条线段是否恰好围成矩形。
样例输入
3
0 0 0 1
1 0 1 1
0 1 1 1
1 0 0 0
0 1 2 3
1 0 3 2
3 2 2 3
1 0 0 1
0 1 1 0
1 0 2 0
2 0 1 1
1 1 0 1
样例输出
YES
YES
NO


这一题题意很简单,但是要写代码实现还是有很多细节需要考虑。
题目给出了4条线段的8个端点,问是否能由这4条线段构成一个面积大于0的矩形。脑海中立马浮现出一个矩形的形状。要构成一个矩形的首要条件是:
1. 有且只有4个互异的顶点
这个条件是显而易见的,如下图(1)给出的4条线段,虽然延长一下能组成矩形,但是很明显如果只由线段组成的话,不是一个矩形。

要判断给出的点是否只有4个点,第一反应是用set集合,只要把题目给出的8个点都加入到set中,判断集合大小是否是4就可以了。
首先给出点的定义:

//点结构体
typedef struct P
{
     int x,y;//两点坐标
     bool operator<(const P& p)const//如果要加入到set中,需要重载<
     {
          //return this->x<p.x&&this->y<p.y;//注意这样会导致(0,0)<(0,1)且(0,1)<(0,0)的情况
          return (this->x<p.x)||((this->x==p.x)&&(this->y<p.y));
     }
     bool operator==(const P&p)const//重载等于比较
     {
          return (this->x==p.x)&&(this->y==p.y);
     }
};

需要注意一点,因为需要把P加入到set中,而set是通过红黑树来排序的,所以需要重载小于<操作符。我最开始重载函数是这样写的

return this->x<p.x&&this->y<p.y;

但是这样会有问题,如果给出两个点(0,0)和(0,1),会得出(0,0)<(0,1)和(0,1)<(0,0)都不成立的结论,也就是说无法给(0,0)和(0,1)排序,也就无法插入到set中,所以需要修改成

return (this->x<p.x)||((this->x==p.x)&&(this->y<p.y));

这样就能判断(0,0)<(0,1)成立了。有关这个问题可以参考这个这个
经过以上的步骤,就把问题转换成已知4个点,问能否由这4个点构成一个矩形的问题了。
此时又可以得出以下两个结论
2. 矩形中某条边和另外3条边的关系是:和其中2条边垂直,和另外1条边平行
3. 且和它平行的那条边不能是重合的边
有的同学可能会说,像上图中的(2)和(3)也是边a和另外2条边垂直、1条边平行啊,但是他们都不是矩形,但是大家别忘了,当我们走到这一步的时候,已经经过了第1个条件的检验,也就是只有4个顶点,你看图(2)和(3)明显不止4个顶点啊。所以结论2成立。
又有同学说,为什么还要结论3呢?因为还可能出现如上图(4)的样子,虽然图中所有边都满足条件2:和2条边垂直、和1条边平行,但是这明显不是一个矩形。因为边a和b重合了。所以结论3还是有必要的。
有了以上3条结论,我们就可以判断给出的4条线段是否能组成一个矩形了。
编程中有一些数学知识需要掌握的是,已知两个线段的4个端点,怎样判断这两条线段的关系:平行?垂直?其他?
很自然想到用斜率,如果k1*k2==-1则垂直,如果k1==k2则平行,否则其他。但是会遇到线段和y轴平行的情况,此时斜率是不存在的,所以需要稍微变一下。
假设线段L1的两个端点分别为(x1,y1)和(x2,y2),线段L2的两个端点分别为(a1,b1)和(a2,b2),则k1*k2==-1可以转换为(y2-y1)*(b2-b1)==-(x2-x1)*(a2-a1)。类似的,k1==k2转换为(y2-y1)*(a2-a1)==(b2-b1)*(x2-x1)。这样就不用担心斜率不存在的问题。
经过以上详细的分析,我们可以写出如下代码:

#include<iostream>
#include<set>
#include <vector>
using namespace std;
//点结构体
typedef struct P
{
     int x,y;//两点坐标
     bool operator<(const P& p)const//如果要加入到set中,需要重载<
     {
          //return this->x<p.x&&this->y<p.y;//注意这样会导致(0,0)<(0,1)且(0,1)<(0,0)的情况
          return (this->x<p.x)||((this->x==p.x)&&(this->y<p.y));
     }
     bool operator==(const P&p)const//重载等于比较
     {
          return (this->x==p.x)&&(this->y==p.y);
     }
};
//线结构体
typedef struct L
{
     P p1,p2;//一条线由两点组成
};
//判断两条线的关系,1:垂直 0:平行 -1:其他
int check_two_line(L l1,L l2)
{
     int x1=l1.p1.x,y1=l1.p1.y,x2=l1.p2.x,y2=l1.p2.y;
     int a1=l2.p1.x,b1=l2.p1.y,a2=l2.p2.x,b2=l2.p2.y;
     if((y2-y1)*(b2-b1)==-(x2-x1)*(a2-a1))//斜率公式的变形
          return 1;
     else if((y2-y1)*(a2-a1)==(b2-b1)*(x2-x1))
          return 0;
     else
          return -1;
}
//判断是否是同一条直线
bool is_same_line(L l1,L l2)
{
     if(((l1.p1==l2.p1)&&(l1.p2==l2.p2))||((l1.p1==l2.p2)&&(l1.p2==l2.p1)))//如果线的两个端点都相同,则是同一条直线
          return true;
     else
          return false;
}
//判断能否组成一个矩形
bool is_rect(vector<L> lines)
{
     int vertical_num,parallel_num;
     for(int i=0;i<4;i++)//每条线都和剩余3条线判断关系
     {
          vertical_num=0;
          parallel_num=0;
          for(int j=0;j<4;j++)
          {
               if(j==i)//不和自己判断
                    continue;
               int rs=check_two_line(lines[i],lines[j]);
               if(rs==-1)
                    return false;
               else if(rs==1)
                    vertical_num++;
               else
               {
                    if(is_same_line(lines[i],lines[j]))//如果是平行线还要判断是否是相同的线
                         return false;
                    parallel_num++;
               }
          }
          if(!(vertical_num==2&&parallel_num==1))//只有当该线和其他2条线垂直,1条线平行时,才能组成矩形
               return false;
     }
     return true;
}
int main()
{
     int T;
     cin>>T;
     while(T--)
     {
          set<P> points;
          vector<L> lines;
          for(int i=0;i<4;i++)
          {
               P p1,p2;
               cin>>p1.x>>p1.y>>p2.x>>p2.y;
               points.insert(p1);
               points.insert(p2);
               L l;
               l.p1=p1;
               l.p2=p2;
               lines.push_back(l);
          }
          if(points.size()!=4)//能组成矩形的必要条件是有且只有4个点,所以用set来判断更方便
               cout<<"NO"<<endl;
          else
          {
               if(is_rect(lines))
                    cout<<"YES"<<endl;
               else
                    cout<<"NO"<<endl;
          }
     }
     return 0;
}

代码提交后AC,用时1MS,内存0MB,还不错。