我们发现对于对答案有影响的点只能有斜率相邻的线能够产生，因此我们可以把斜率相同的放在一组，相邻计算即可。
class Solution { public: static bool cmp(pair<int,int> x,const pair<int,int> y){ if(x.first!=y.first)return x.first<y.first; else return x.second<y.second; } double minRecSize(vector<vector<int>>& lines) { map<int,pair<int,int> > sq;//up down max pair<int,int> st[123456]; int len=(int)lines.size(); for(int i=0;i<(int)lines.size();i++){ st[i]=make_pair(lines[i][0],lines[i][1]); } //cout<<st[0].first<<" "<<st[0].second<<endl; sort(st,st+len,cmp); double l,u,r,d; l=u=r=d=0; int count=0; sq[st[0].first]=make_pair(st[0].second,st[0].second); int last=st[0].first; //cout<<sq[last].first<<" "<<sq[last].second<<endl; for(int i=1;i<len;i++){ //cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl; if(st[i].first==st[i-1].first){ int q=st[i].first; int s=st[i].second; if(sq[q].first<s)sq[q].first=s; if(sq[q].second>s)sq[q].second=s; //crazy if(q==last)continue; int dd1=st[i].second-sq[last].first; int dd2=st[i].second-sq[last].second; int qq=st[i].first-last; double x1= -1.0*dd1/qq; double x2=-1.0*dd2/qq; double y1= st[i].first*x1+st[i].second; double y2=st[i].first*x2+st[i].second; if(count==0){ l=r=x1; u=d=y1; } if(x1>r)r=x1; if(x1<l)l=x1; if(y1>u)u=y1; if(y1<d)d=y1; if(x2>r)r=x2; if(x2<l)l=x2; if(y2>u)u=y2; if(y2<d)d=y2; count++; continue; } last=st[i-1].first; //bug sq[st[i].first]=make_pair(st[i].second,st[i].second); int dd1=st[i].second-sq[last].first; int dd2=st[i].second-sq[last].second; int q=st[i].first-last; double x1= -1.0*dd1/q; double x2=-1.0*dd2/q; double y1= st[i].first*x1+st[i].second; double y2=st[i].first*x2+st[i].second; if(count==0){ l=r=x1; u=d=y1; } if(x1>r)r=x1; if(x1<l)l=x1; if(y1>u)u=y1; if(y1<d)d=y1; if(x2>r)r=x2; if(x2<l)l=x2; if(y2>u)u=y2; if(y2<d)d=y2; count++; } if(!count)return 0; else return fabs(u-d)*fabs(l-r); } };