怎么做网站解析,酒泉网站建设与制作,网络科技,随机关键词生成器题目#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id1069 发现 n 可以 n^2 。所以枚举对角线#xff0c;分开的两部分三角形就可以旋转卡壳了。 注意坐标是实数。忘了改生成函数调了 2h …… 也不知道用不用管凸包上只有 3 个点的情况。反正这样的话就是枚举一…题目https://www.lydsy.com/JudgeOnline/problem.php?id1069 发现 n 可以 n^2 。所以枚举对角线分开的两部分三角形就可以旋转卡壳了。 注意坐标是实数。忘了改生成函数调了 2h …… 也不知道用不用管凸包上只有 3 个点的情况。反正这样的话就是枚举一个凹进去的三角形的最小面积罢了。 #includecstdio
#includecstring
#includealgorithm
#define db double
using namespace std;
const int N2005; const db INF4e105;
int n,tot,sta[N],top;db ans;
struct Node{db x,y;Node(db a0,db b0):x(a),y(b) {}///db!!!!!!bool operator (const Node b)const{return xb.x||(xb.xyb.y);}Node operator- (const Node b)const{return Node(x-b.x,y-b.y);}
}t[N],a[N];
db Mx(db a,db b){return ab?a:b;}
db Mn(db a,db b){return ab?a:b;}
db cross(Node u,Node v){return u.x*v.y-u.y*v.x;}
void get_hl()
{sort(t1,ttot1);for(int i1;itot;i){while(top1cross(t[sta[top]]-t[i],t[sta[top-1]]-t[i])0)top--;sta[top]i;}for(int itot-1,lmtop;i;i--){while(toplmcross(t[sta[top]]-t[i],t[sta[top-1]]-t[i])0)top--;sta[top]i;}ntop-1;for(int i1;in;i)a[i]t[sta[i]];
}
void upd(int x){if(xn)x-n;if(x0)xn;}
void rtc(int st)
{int p0st1,p1st3;upd(p1);a[n1]a[1];//for(int crst2;crn;cr)//n is ok not !(st-1){Node da[cr]-a[st];while(cross(a[p01]-a[st],d)cross(a[p0]-a[st],d))p0,upd(p0);while(cross(d,a[p11]-a[st])cross(d,a[p1]-a[st]))p1,upd(p1);ansMx(ans,cross(a[p0]-a[st],d)cross(d,a[p1]-a[st]));}
}
int main()
{scanf(%d,tot);for(int i1;itot;i)scanf(%lf%lf,t[i].x,t[i].y);get_hl();if(n4){for(int i1,jn-2;ij;i)rtc(i);//n-2 is okprintf(%.3f\n,ans/2);}else{ansINF;bool flag0;for(int i1;in;i){flag0;for(int j1;j3;j)if(t[i].xa[j].xt[i].ya[j].y){flag1;break;}if(flag)continue;ansMn(ans,cross(t[i]-a[1],t[i]-a[2]));ansMn(ans,cross(t[i]-a[2],t[i]-a[3]));ansMn(ans,cross(t[i]-a[3],t[i]-a[1]));}printf(%.3f\n,(cross(a[2]-a[1],a[3]-a[1])-ans)/2);}return 0;
} 转载于:https://www.cnblogs.com/Narh/p/10146382.html
