http://acm.pku.edu.cn/JudgeOnline/problem?id=1468時間限制竟然是50000ms ,而n<=5000, 直接搜索時間復雜度是O(n^2) ,完全可能符合條件,直接暴力解決.
Source
Problem Id:1468 User Id:lnmm
Memory:144K Time:2718MS
Language:C++ Result:Accepted
1
#include"stdio.h"
2
struct rec
{
3
int x1,x2,y1,y2;
4
}rec [5001];
5
6bool cover(int i,int j)
7{
8 if((rec[i].x1>=rec[j].x1)&&(rec[i].x2<=rec[j].x2)&&(rec[i].y1>=rec[j].y1)&&(rec[i].y2<=rec[j].y2))return true;
9 else return false;
10}
11
12void main()
13{
14 int n,i,k,j;
15 while(scanf("%d",&n)!=EOF)
16
{
17 k=0;
18 for(i=1;i<=n;i++)
19 scanf("%d%d%d%d",&rec[i].x1,&rec[i].x2,&rec[i].y1,&rec[i].y2);
20 for(i=1;i<=n;i++)
21 for(j=1;j<=n;j++)
22 if(i!=j&&cover(i,j)){k++;break; }
23 printf("%d\n",k);
24
25
26
}
27
28}
29