https://www.luogu.org/problemnew/show/P1034
可能是数据太水了瞎搞都可以过.
判断两个平行于坐标轴的矩形相交 (含顶点与边相交) 的代码一并附上.
记得这里的 xy 和 udlr 是指数学上的坐标轴.
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- struct Point{
- int x,y;
- Point(int x=0,int y=0){
- this->x=x,this->y=y;
- }
- }p[51];
- struct Rectangle{
- int u,d,l,r;
- Rectangle(){
- u=d=l=r=-1;
- }
- bool inside(Point p){
- if(p.x>=l&&p.x<=r&&p.y>=d&&p.y<=u)
- return true;
- return false;
- }
- bool intersect_help(Rectangle r2){
- Point r1p1(l,u);
- if(r2.inside(r1p1))
- return 1;
- Point r1p2(r,u);
- if(r2.inside(r1p2))
- return 1;
- Point r1p3(r,d);
- if(r2.inside(r1p3))
- return 1;
- Point r1p4(l,d);
- if(r2.inside(r1p4))
- return 1;
- return 0;
- }
- bool intersect(Rectangle r2){
- if(u==-1||r2.u==-1)
- return 0;
- if(intersect_help(r2))
- return 1;
- if(r2.intersect_help(*this))
- return 1;
- if(l<=r2.l&&r>=r2.r&&u<=r2.u&&d>=r2.d)
- return 1;
- if(r2.l<=l&&r2.r>=r&&r2.u<=u&&r2.d>=d)
- return 1;
- return 0;
- }
- int area(){
- return (r-l)*(u-d);
- }
- void extend(Point p){
- if(u==-1){
- l=r=p.x;
- u=d=p.y;
- return;
- }
- else{
- l=min(l,p.x);
- r=max(r,p.x);
- u=max(u,p.y);
- d=min(d,p.y);
- return;
- }
- }
- void show(){
- printf("u=%d d=%d l=%d r=%d\n",u,d,l,r);
- }
- };
- int n,k;
- int ans=0x3f3f3f3f;
- void dfs4(int id,Rectangle r1,Rectangle r2,Rectangle r3,Rectangle r4){
- //r1.show(),r2.show(),r3.show(),r4.show();
- //printf("---------\n");
- if(id>n){
- ans=min(ans,r1.area()+r2.area()+r3.area()+r4.area());
- return;
- }
- Point pi=p[id];
- if(r1.inside(pi)||r2.inside(pi)||r3.inside(pi)||r4.inside(pi))
- dfs4(id+1,r1,r2,r3,r4);
- else{
- Rectangle rr1=r1;
- rr1.extend(pi);
- if(rr1.intersect(r2)||rr1.intersect(r3)||rr1.intersect(r4))
- ;
- else{
- dfs4(id+1,rr1,r2,r3,r4);
- }
- Rectangle rr2=r2;
- rr2.extend(pi);
- if(rr2.intersect(r1)||rr2.intersect(r3)||rr2.intersect(r4))
- ;
- else{
- dfs4(id+1,r1,rr2,r3,r4);
- }
- Rectangle rr3=r3;
- rr3.extend(pi);
- if(rr3.intersect(r1)||rr3.intersect(r2)||rr3.intersect(r4))
- ;
- else{
- dfs4(id+1,r1,r2,rr3,r4);
- }
- Rectangle rr4=r4;
- rr4.extend(pi);
- if(rr4.intersect(r1)||rr4.intersect(r2)||rr4.intersect(r3))
- ;
- else{
- dfs4(id+1,r1,r2,r3,rr4);
- }
- }
- }
- void dfs3(int id,Rectangle r1,Rectangle r2,Rectangle r3){
- //r1.show(),r2.show(),r3.show();
- //printf("---------\n");
- if(id>n){
- ans=min(ans,r1.area()+r2.area()+r3.area());
- return;
- }
- Point pi=p[id];
- if(r1.inside(pi)||r2.inside(pi)||r3.inside(pi))
- dfs3(id+1,r1,r2,r3);
- else{
- Rectangle rr1=r1;
- rr1.extend(pi);
- if(rr1.intersect(r2)||rr1.intersect(r3))
- ;
- else{
- dfs3(id+1,rr1,r2,r3);
- }
- Rectangle rr2=r2;
- rr2.extend(pi);
- if(rr2.intersect(r1)||rr2.intersect(r3))
- ;
- else{
- dfs3(id+1,r1,rr2,r3);
- }
- Rectangle rr3=r3;
- rr3.extend(pi);
- if(rr3.intersect(r1)||rr3.intersect(r2))
- ;
- else{
- dfs3(id+1,r1,r2,rr3);
- }
- }
- }
- void dfs2(int id,Rectangle r1,Rectangle r2){
- if(id>n){
- //r1.show(),r2.show();
- int tans=r1.area()+r2.area();
- ans=min(ans,tans);
- //printf("tans=%d\n---------\n",tans);
- return;
- }
- Point pi=p[id];
- if(r1.inside(pi)||r2.inside(pi))
- dfs2(id+1,r1,r2);
- else{
- Rectangle rr1=r1;
- rr1.extend(pi);
- if(rr1.intersect(r2))
- ;
- else{
- dfs2(id+1,rr1,r2);
- }
- Rectangle rr2=r2;
- rr2.extend(pi);
- if(rr2.intersect(r1))
- ;
- else{
- dfs2(id+1,r1,rr2);
- }
- }
- }
- void dfs(int id,Rectangle r1){
- //r1.show();
- //printf("---------\n");
- if(id>n){
- ans=min(ans,r1.area());
- return;
- }
- Point pi=p[id];
- if(r1.inside(pi))
- dfs(id+1,r1);
- else{
- Rectangle rr1=r1;
- rr1.extend(pi);
- dfs(id+1,rr1);
- }
- }
- int main(){
- scanf("%d%d",&n,&k);
- for(int i=1;i<=n;i++){
- scanf("%d%d",&p[i].x,&p[i].y);
- }
- Rectangle r;
- switch(k){
- case 1:
- dfs(1,r);
- break;
- case 2:
- dfs2(1,r,r);
- break;
- case 3:
- dfs3(1,r,r,r);
- break;
- case 4:
- dfs4(1,r,r,r,r);
- }
- printf("%d\n",ans);
- }
加入最优性剪枝: 22ms, 快了 3 倍?
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- struct Point{
- int x,y;
- Point(int x=0,int y=0){
- this->x=x,this->y=y;
- }
- }p[51];
- struct Rectangle{
- int u,d,l,r;
- Rectangle(){
- u=d=l=r=-1;
- }
- bool inside(Point p){
- if(p.x>=l&&p.x<=r&&p.y>=d&&p.y<=u)
- return true;
- return false;
- }
- bool intersect_help(Rectangle r2){
- Point r1p1(l,u);
- if(r2.inside(r1p1))
- return 1;
- Point r1p2(r,u);
- if(r2.inside(r1p2))
- return 1;
- Point r1p3(r,d);
- if(r2.inside(r1p3))
- return 1;
- Point r1p4(l,d);
- if(r2.inside(r1p4))
- return 1;
- return 0;
- }
- bool intersect(Rectangle r2){
- if(u==-1||r2.u==-1)
- return 0;
- if(intersect_help(r2))
- return 1;
- if(r2.intersect_help(*this))
- return 1;
- if(l<=r2.l&&r>=r2.r&&u<=r2.u&&d>=r2.d)
- return 1;
- if(r2.l<=l&&r2.r>=r&&r2.u<=u&&r2.d>=d)
- return 1;
- return 0;
- }
- int area(){
- return (r-l)*(u-d);
- }
- void extend(Point p){
- if(u==-1){
- l=r=p.x;
- u=d=p.y;
- return;
- }
- else{
- l=min(l,p.x);
- r=max(r,p.x);
- u=max(u,p.y);
- d=min(d,p.y);
- return;
- }
- }
- void show(){
- printf("u=%d d=%d l=%d r=%d\n",u,d,l,r);
- }
- };
- int n,k;
- int ans=0x3f3f3f3f;
- void dfs4(int id,Rectangle r1,Rectangle r2,Rectangle r3,Rectangle r4){
- //r1.show(),r2.show(),r3.show(),r4.show();
- //printf("---------\n");
- int tans=r1.area()+r2.area()+r3.area()+r4.area();
- if(tans>=ans)
- return;
- if(id>n){
- ans=min(ans,tans);
- return;
- }
- Point pi=p[id];
- if(r1.inside(pi)||r2.inside(pi)||r3.inside(pi)||r4.inside(pi))
- dfs4(id+1,r1,r2,r3,r4);
- else{
- Rectangle rr1=r1;
- rr1.extend(pi);
- if(rr1.intersect(r2)||rr1.intersect(r3)||rr1.intersect(r4))
- ;
- else{
- dfs4(id+1,rr1,r2,r3,r4);
- }
- Rectangle rr2=r2;
- rr2.extend(pi);
- if(rr2.intersect(r1)||rr2.intersect(r3)||rr2.intersect(r4))
- ;
- else{
- dfs4(id+1,r1,rr2,r3,r4);
- }
- Rectangle rr3=r3;
- rr3.extend(pi);
- if(rr3.intersect(r1)||rr3.intersect(r2)||rr3.intersect(r4))
- ;
- else{
- dfs4(id+1,r1,r2,rr3,r4);
- }
- Rectangle rr4=r4;
- rr4.extend(pi);
- if(rr4.intersect(r1)||rr4.intersect(r2)||rr4.intersect(r3))
- ;
- else{
- dfs4(id+1,r1,r2,r3,rr4);
- }
- }
- }
- void dfs3(int id,Rectangle r1,Rectangle r2,Rectangle r3){
- //r1.show(),r2.show(),r3.show();
- //printf("---------\n");
- int tans=r1.area()+r2.area()+r3.area();
- if(tans>=ans)
- return;
- if(id>n){
- ans=min(ans,tans);
- return;
- }
- Point pi=p[id];
- if(r1.inside(pi)||r2.inside(pi)||r3.inside(pi))
- dfs3(id+1,r1,r2,r3);
- else{
- Rectangle rr1=r1;
- rr1.extend(pi);
- if(rr1.intersect(r2)||rr1.intersect(r3))
- ;
- else{
- dfs3(id+1,rr1,r2,r3);
- }
- Rectangle rr2=r2;
- rr2.extend(pi);
- if(rr2.intersect(r1)||rr2.intersect(r3))
- ;
- else{
- dfs3(id+1,r1,rr2,r3);
- }
- Rectangle rr3=r3;
- rr3.extend(pi);
- if(rr3.intersect(r1)||rr3.intersect(r2))
- ;
- else{
- dfs3(id+1,r1,r2,rr3);
- }
- }
- }
- void dfs2(int id,Rectangle r1,Rectangle r2){
- int tans=r1.area()+r2.area();
- if(tans>=ans)
- return;
- if(id>n){
- //r1.show(),r2.show();
- ans=min(ans,tans);
- //printf("tans=%d\n---------\n",tans);
- return;
- }
- Point pi=p[id];
- if(r1.inside(pi)||r2.inside(pi))
- dfs2(id+1,r1,r2);
- else{
- Rectangle rr1=r1;
- rr1.extend(pi);
- if(rr1.intersect(r2))
- ;
- else{
- dfs2(id+1,rr1,r2);
- }
- Rectangle rr2=r2;
- rr2.extend(pi);
- if(rr2.intersect(r1))
- ;
- else{
- dfs2(id+1,r1,rr2);
- }
- }
- }
- void dfs(int id,Rectangle r1){
- //r1.show();
- //printf("---------\n");
- int tans=r1.area();
- if(tans>=ans)
- return;
- if(id>n){
- ans=min(ans,r1.area());
- return;
- }
- Point pi=p[id];
- if(r1.inside(pi))
- dfs(id+1,r1);
- else{
- Rectangle rr1=r1;
- rr1.extend(pi);
- dfs(id+1,rr1);
- }
- }
- int main(){
- scanf("%d%d",&n,&k);
- for(int i=1;i<=n;i++){
- scanf("%d%d",&p[i].x,&p[i].y);
- }
- Rectangle r;
- switch(k){
- case 1:
- dfs(1,r);
- break;
- case 2:
- dfs2(1,r,r);
- break;
- case 3:
- dfs3(1,r,r,r);
- break;
- case 4:
- dfs4(1,r,r,r,r);
- }
- printf("%d\n",ans);
- }
来源: http://www.bubuko.com/infodetail-3012032.html