60pts求助
查看原帖
60pts求助
545032
XY_world楼主2023/9/1 15:20

如果加check_jx函数的话就是80分,挂第三个点; 如果不加的话就是60分,挂地4、5个点

#include <iostream>
using namespace std;
int n,k,zans=1e9;
struct ju_xing{
	int x1,y1,x2,y2;
	bool is_used;
	
	ju_xing() {
		is_used = false;
		return;
	}
}s[5];

struct dian{
	int x,y;
}a[50];

bool is_cover(int id){
	for(int i=1;i<=k;i++){
		if(s[id].is_used&&s[i].x1<=a[id].x&&a[id].x<=s[i].x2&&s[i].y1<=a[id].y&&a[id].y<=s[i].y2) return true;
	}
	return false;
}

bool check(int id,int x,int y){
	if(s[id].x1<=x&&x<=s[id].x2&&s[id].y1<=y&&y<=s[id].y2) return true;
	return false;
}
bool check_jx(int id){
	for(int i=1;i<=k;i++){
		if(i==id) continue;
		if(s[i].is_used){
			if(check(i,s[id].x1,s[id].y1)) return true;
			if(check(i,s[id].x2,s[id].y1)) return true;
			if(check(i,s[id].x1,s[id].y2)) return true;
			if(check(i,s[id].x2,s[id].y2)) return true;
		}
	}
	return false;
}
int getans(){
	int QwQ=0;
	for(int i=1;i<=k;i++) QwQ+=(s[i].x2-s[i].x1)*(s[i].y2-s[i].y1);
	return QwQ;
}
void dfs(int id,int ans){
	if(ans>=zans) return;
	if(id>n){
		zans=ans;
		return ;
	}
	if(is_cover(id)){
		dfs(id+1,ans);
		return ;
    }
	for(int i=1;i<=k;i++){
		ju_xing now=s[i];
		if(s[i].is_used==false){
			s[i].x1=a[id].x;
			s[i].y1=a[id].y;
			s[i].x2=a[id].x;
			s[i].y2=a[id].y;
			s[i].is_used=true;
			//s[i] = (ju_xing){a[id].x,a[id].y,a[id].x,a[id].y}
		}else{
			s[i].x1=min(s[i].x1,a[id].x);
			s[i].y1=min(s[i].y1,a[id].y);
			s[i].x2=max(s[i].x2,a[id].x);
			s[i].y2=max(s[i].y2,a[id].y);
		}
		if(check_jx(i)){
			s[i]=now;
			return;
		}
		dfs(id+1,getans());
		s[i]=now;
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	dfs(1,0);
	cout<<zans;
	return 0;
}
2023/9/1 15:20
加载中...