http://www.usaco.org/index.php?page=viewproblem2&cpid=642
题意：
给n个点，删除3个后使得围住所有点的矩形的面积最小。
解析：
假设已经得到了当前的矩形，每次删除点肯定是边界上的。所以所有可能删除的点位：x最小的3个，x最大的3个，y最小的3个，y最大的3个。
用set维护一下即可。
代码：
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) typedef long long LL; #define pill pair<int,int> const int maxn=5e4+9; void show(int i){ cout<<"show "<<i<<endl; } int a[maxn],b[maxn]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n;cin>>n; set<pill>sx,sy; rep(i,1,n){ cin>>a[i]>>b[i]; sx.insert({a[i],i}); sy.insert({b[i],i}); } vector<int>s; auto it=sx.begin(); rep(i,1,3){ s.push_back((*it).second); ++it; } it=sx.end(); it--; rep(i,1,3){ s.push_back((*it).second); --it; } it=sy.begin(); rep(i,1,3){ s.push_back((*it).second); ++it; } it=sy.end(); it--; rep(i,1,3){ s.push_back((*it).second); --it; } sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end()); LL ans=1e18; int num=s.size(); // for(auto p:s){ // show(p); // } // // // for(auto p:sx){ // cout<<"x:"<<p.first<<" id:"<<p.second<<endl; // } // for(auto p:sy){ // cout<<"y:"<<p.first<<" id:"<<p.second<<endl; // } rep(i,0,num-3){ sx.erase({a[s[i]],s[i]}); sy.erase({b[s[i]],s[i]}); rep(j,i+1,num-2){ sx.erase({a[s[j]],s[j]}); sy.erase({b[s[j]],s[j]}); rep(k,j+1,num-1){ sx.erase({a[s[k]],s[k]}); sy.erase({b[s[k]],s[k]}); // if(i==0&&j==4&&k==5){ // for(auto p:sx){ // cout<<"x:"<<p.first<<" id:"<<p.second<<endl; // } // for(auto p:sy){ // cout<<"y:"<<p.first<<" id:"<<p.second<<endl; // } // } LL l,r,u,d; it=sx.begin(); l=(*it).first; it=sx.end(); it--; r=(*it).first; it=sy.begin(); d=(*it).first; it=sy.end(); it--; u=(*it).first; ans=min(ans,(r-l)*(u-d)); //cout<<"erase "<<s[i]<<" "<<s[j]<<" "<<s[k]<<" ans = "<<ans<<endl; sx.insert({a[s[k]],s[k]}); sy.insert({b[s[k]],s[k]}); } sx.insert({a[s[j]],s[j]}); sy.insert({b[s[j]],s[j]}); } sx.insert({a[s[i]],s[i]}); sy.insert({b[s[i]],s[i]}); } cout<<ans<<endl; }