题目描述:给你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; }