「FJ2015集训」签到题
「问题描述」
给定一个n个点的严格凸多边形（各个内角<180°），现在要切出两个非退化三角形（三点不共线），要求两个三角形顶点必须是凸多边形的顶点，且三角形不可相交（但是点或边可以重合）。求两个三角形面积之差的最大值。
「输入格式」
第一行，一个整数N。
第二到N+1行，每行两个整数xi,yi，表示多边形的一个点，保证顶点按顺时针或逆时针顺序给出。
「输出格式」
输出答案，精确到小数点后1位。
「样例输入1」
4
0 0
0 1
1 2
1 0
「样例输出1」
0.5
「样例输入2」
5
0 0
-1 6
0 7
2 8
7 7
「样例输出2」
24.0
「数据规模与约定」
对于15%的数据，N<=10
对于45%的数据，N<=307
对于100%的数据，4<=N<=5000， 0<=|xi|,|yi|<=10^8
题解
发现最小的三角形三个顶点在凸多边形上是相邻的，枚举最大三角形的一条边旋转卡壳的时候顺便记录当前能取的最小三角形
复杂度n^2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<map> #include<set> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,nxt[5005],pre[5005]; ll ans; ll mn[5005]; struct P{ ll x,y; friend ll operator*(P a,P b){ return a.x*b.y-a.y*b.x; } friend P operator-(P a,P b){ return (P){a.x-b.x,a.y-b.y}; } }p[5005]; int main() { // freopen("k.in","r",stdin); // freopen("k.out","w",stdout); n=read(); for(int i=0;i<n;i++)nxt[i]=i+1,pre[i]=i-1; nxt[n-1]=0;pre[0]=n-1; for(int i=0;i<n;i++) p[i].x=read(),p[i].y=read(); for(int i=0;i<n;i++) mn[i]=abs((p[i]-p[pre[i]])*(p[nxt[i]]-p[pre[i]])); for(int i=0;i<n;i++) { int k=nxt[nxt[i]]; ll T=(ll)1e60; for(int j=nxt[i];j!=i;j=nxt[j]) { while(abs((p[j]-p[i])*(p[k]-p[i]))<abs((p[j]-p[i])*(p[nxt[k]]-p[i])))k=nxt[k]; ll t=abs((p[j]-p[i])*(p[k]-p[i])); if(mn[pre[j]]<T)T=mn[pre[j]]; if(t-T>ans)ans=t-T; } } if(ans&1) { printf("%lld",ans/2); puts(".5"); } else { printf("%lld",ans/2); puts(".0"); } // fclose(stdin); // fclose(stdout); return 0; } |
计数器 9299970
OI 课件=>
OI 课件=>
orz黄学长，请问这题在哪里可以提交吗？