Axis-Parallel Rectangle

D - Axis-Parallel Rectangle

Time limit : 2sec /Memory limit : 256MB
Score :400points

Problem Statement

We haveNpoints in a two-dimensional plane.

The coordinates of thei-th point(1≤i≤N)are(xi,yi).

Let us consider a rectangle whose sides are parallel to the coordinate axes that containsKor more of theNpoints in its interior.

Here, points on the sides of the rectangle are considered to be in the interior.

Find the minimum possible area of such a rectangle.

Constraints

• 2≤K≤N≤50
• −109≤xi,yi≤109(1≤i≤N)
• xi≠xj(1≤i<j≤N)
• yi≠yj(1≤i<j≤N)
• All input values are integers. (Added at 21:50 JST)

Input

Input is given from Standard Input in the following format:

N K  
x1 y1
:  
xN yN

Output

Print the minimum possible area of a rectangle that satisfies the condition.

Sample Input 1

Copy

4 4
1 4
3 3
6 2
8 1

Sample Output 1

Copy

21

One rectangle that satisfies the condition with the minimum possible area has the following vertices:(1,1),(8,1),(1,4)and(8,4).

Its area is(8−1)×(4−1)=21.

Sample Input 2

Copy

4 2
0 0
1 1
2 2
3 3

Sample Output 2

Copy

1

Sample Input 3

Copy

4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

Sample Output 33999999996000000001Watch out for integer overflows.// N 个点，选出一个最小的矩形，包括至少 k 个点，求这最小的矩形的面积// 枚举，疯狂枚举就行

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define MOD 998244353
 4 #define INF 0x3f3f3f3f3f3f3f3f
 5 #define LL long long
 6 #define MX 55
 7 struct Node
 8 {
 9     LL x, y;
10     bool operator < (const Node &b)const{
11         return x<b.x;
12     }
13 }pt[MX];
14 
15 int k, n;
16 
17 int main()
18 {
19     scanf("%d%d",&n,&k);
20     for (int i=1;i<=n;i++)
21         scanf("%lld%lld",&pt[i].x, &pt[i].y);
22     sort(pt+1,pt+1+n);
23     LL area = INF;
24     for (int i=1;i<=n;i++)
25     {
26         for (int j=i+1;j<=n;j++)
27         {
28             LL miny = min(pt[i].y, pt[j].y);
29             LL maxy = max(pt[i].y, pt[j].y);
30             for (int q=1;q<=n;q++)
31             {
32                 if (pt[q].y>maxy||pt[q].y<miny) continue;
33                 int tot = 0;
34                 for (int z=q;z<=n;z++)
35                 {
36                     if (pt[z].y>maxy||pt[z].y<miny) continue;
37                     tot++;
38                     if (tot>=k)
39                         area = min(area, (maxy-miny)*(pt[z].x-pt[q].x));
40                 }
41             }
42         }
43     }
44     printf("%lldn",area);
45     return 0;
46 }

View Code

原文链接: https://www.cnblogs.com/haoabcd2010/p/7673891.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍