首页 > 代码库 > ural1097 Square Country 2
ural1097 Square Country 2
Square Country 2
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
The Square Parliament of the Square country (recall the corresponding problem from the USU 2001 personal contest) has decreed that the National Square Park be created. Of course, the Park should occupy a large square. Unfortunately, at the moment a lot of square citizens have invested (with the help of last championship‘s participants) their quadrics into the land so that a part of the country is already occupied. It is now impossible to find a land for the Park without affecting interests of the private owners. Thus some of the pieces of land must be expropriated.
To avoid social unrest the Parliament has to locate the Park so that the interests of as less important as possible citizens were affected. It is better to expropriate land from a thousand of simple citizens than from one member of the Parliament or from one bank-owner.
The occupied pieces of land are marked with numbers from 1 to 100 according to importance of the owner. So all free land and pieces of land belonging to honest tax-payers are marked with number 1, the land belonging to members of the Parliament is marked with 98, possessions of great businessmen are marked with 99, and the property of the square President is marked with 100.
Input
The first line contains the number L, which is the length of a side of the Square country (in meters), and the number A, which is the length of a side of the Park (1 ≤ A ≤ L ≤ 10000). The next line contains the number M (1 ≤ M ≤ 100) of occupied pieces of land (according to the square rules a piece of land is a square with integer coordinates of corners and its sides are parallel to the axes).
The next M lines contain information about these pieces of land: importance of the owner, length of the square‘s side and the coordinates of the lower left corner, which are integers from 1 to L (the coordinates of the lower left corner of the Square country itself are 1,1). Each piece of land is contained in the country and may intersect another piece of land only along its boundary.
Note that land marked with number 1 (that is of importance 1) is not mentioned in the list altogether. Besides, some pieces of land belong to the members of (not square) Jury who helped to formulate the previous problem. This land is marked with number 255 and cannot be expropriated at all.
Output
You should output the least possible importance of land which must be expropriated (a number from 1 to 100) or the word IMPOSSIBLE if it is impossible to create the Park not involving land of importance more than 100. The number and area of expropriated pieces of land are not important. You should only take into account importance of the most important of the affected land-owners.
Sample
| input | output |
|---|---|
5 3694 2 4 13 1 1 12 1 1 22 2 2 1100 1 2 4255 1 5 5 | 3
|
分析：参考http://blog.csdn.net/jyysc2010/article/details/9968813；
暴力枚举矩形顶点即可，复杂度o(M3);
不过感觉数据略有问题；
代码：
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=1e2+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}int n,m,k,t,b[maxn],c[maxn],ans,p,q;struct node{ int id,x,y,z; node(){} node(int _id,int _z,int _x,int _y) { id=_id,x=_x,y=_y,z=_z; }}a[maxn];int main(){ int i,j; ans=1000; scanf("%d%d%d",&n,&m,&k); rep(i,1,k) { int b,c,d,e; scanf("%d%d%d%d",&b,&c,&d,&e); a[i]=node(b,c,d,e); } a[0]=node(0,1,0,0); rep(i,0,k)rep(j,0,k) { int x=a[i].x+a[i].z,y=a[j].y+a[j].z,now=1; if(x+m-1>n||y+m-1>n)continue; rep(t,1,k) { if(a[t].x>x+m-1||a[t].y>y+m-1||a[t].x+a[t].z-1<x||a[t].y+a[t].z-1<y)continue; now=max(now,a[t].id); } ans=min(ans,now); } if(ans<=100)printf("%d\n",ans); else puts("IMPOSSIBLE"); //system("Pause"); return 0;}
ural1097 Square Country 2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。