题目描述:给你n个矩形的长宽高,你最多可以选择两个面相同的矩形合并,现在让求出这几个矩形的最大内切圆(可以选一个也可以选两个)
1 ≤ n ≤ 105
分析:对于一个矩形没啥好说的直接找最短边输出就好,考虑两个矩形合并的情况,两个矩形当且只有合并的面没有这两个矩形的最短边时这两个矩形 内切圆才有变化否则还是这两个之中的一个内切圆大小
且当变化时有两种情况要么还是这里最小边,要么不是,不是的话就是相同面的次小边;当时没想出来 太弱了~~
ac代码:
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y,z;
int index;
node(){}
node(int x1,int y1,int z1,int index1){
index=index1;
x=max(y1,max(x1,z1));
z=min(y1,min(x1,z1));
y=x1+y1+z1-x-z;
}
bool operator <(node a){
if(x==a.x){
if(y==a.y)return z>a.z;
else return y>a.y;
}
else return x<a.x;
}
}rec[100005];
int n;
int main(){
// freopen("1.txt","r",stdin);
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
long long ma=0,index=1;
for(int i=1;i<=n;i++){
int x,y,z;
cin>>x>>y>>z;
node temp(x,y,z,i);
rec[i]=temp;
if(rec[i].z>ma){
index=i;
ma=rec[i].z;
}
}
sort(rec+1,rec+1+n);
long long mama=0,flag=0;
pair<int,int> index1;
for(int i=1;i<n;i++)
if(rec[i].x==rec[i+1].x&&rec[i].y==rec[i+1].y)
if(mama<min(rec[i].z+rec[i+1].z,rec[i].y)){
mama=min(rec[i].z+rec[i+1].z,rec[i].y);
index1=make_pair(rec[i].index,rec[i+1].index);
}
if(mama<=ma)cout<<1<<'\n'<<index<<endl;
else cout<<2<<'\n'<<index1.first<<' '<<index1.second<<endl;
}

京公网安备 11010502036488号