2019/5/13 day2 解题日志

2019-05-13

字数统计: 1.9k字 | 阅读时长: 10分

day2

给$n$个点，从中选$4$个点组成四边形，求最小四边形面积，$n \lt 2000$。
给$n$个点，从中选$4$个点组成四边形，求最大四边形面积，$n \lt 2000$。

最小四边形

思路

先考虑三角形。要使得三角形面积最小，这个面积的贡献点一定是以其中一个点为中心，旋转一个很小的弧度得到的。
拓展到四边形，可以猜测依旧有如上性质。
所以不妨枚举所有点$a$，以$a$为原点进行极角排序，那么得到的$p[]$一定都是有序排列的，且相邻的$b,c,d$和$a$组成的四边形一定是最小面积的可行解。
由于这个四边形可以是凹的，所以分类讨论：

$S_{abc} + S_{acd} > S_{abd} $，说明四边形是凸的；
否则直接得出 $min( S_{abc}+min(S_{acd},S_{bcd}),S_{acd}+S_{bcd} )$，求出最小的凹四边形。

tips

注意极角排序时，尽量避免使用$atan2$函数，改用叉积排序，因为$atan2$的效率非常低。

代码

const int maxn = 6005;
struct point{
    ll x,y;
    point(ll x=0,ll y=0):x(x),y(y){}
    bool operator<(const point &b)const{if(x<b.x)return 1;if(x>b.x)return 0;return y<b.y;}
    bool operator==(const point &b)const{return x==b.x&&y==b.y;}
    point operator -(const point &b)const{return point(x-b.x,y-b.y);}
    ll operator ^(const point &b)const{return (x*b.y-y*b.x);}
};
bool cmp3(point a,point b){return (a^b)>0;}
ll mj(point a,point b,point c){return abs((b-a)^(c-a));}
ll ok(point a,point b,point c,point d){
    ll abc=mj(a,b,c);
    ll acd=mj(a,c,d);
    ll abd=mj(a,b,d);
    ll bcd=mj(b,c,d);
    if(abc+acd>abd)return abc+acd;
    return min(abc+min(bcd,acd) ,bcd+acd );
}

    for(int i=1;i<=n;i++)scanf("%lld%lld",&p[i].x,&p[i].y);
    ll A=0,B=9e18;
    point pp[maxn];
    for(int i=1;i<=n;i++){
        point mi=p[i];
        int cnt=0;
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            pp[++cnt]=p[j]-mi;
        }sort(pp+1,pp+1+cnt,cmp3);
        for(int j=1;j+2<=cnt;j++){
            B=min(B,ok(point(0,0),pp[j],pp[j+1],pp[j+2]));
        }
    }

最大四边形

思路

首先可以从三角形推断，最大三角形落在凸包上，那么最大四边形肯定也落在凸包上。
然后构建出凸包，用旋转卡壳求出以点$a,b$为对角线得到的最大四边形便可，注意另外两点$c,d$一定是分布在$a,b$的两侧，且这个四边形一定是凸包。
如果不存在这样的四边形，说明凸包大小为3，那么只需要在剩余点里找一个点，然后构建凹四边形，再算答案便可。

tips

凸包板子一定要检查一遍！！！

两个子问题合二为一的代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=6005;
struct point{
    ll x,y;
    point(ll x=0,ll y=0):x(x),y(y){}
    bool operator<(const point &b)const{if(x<b.x)return 1;if(x>b.x)return 0;return y<b.y;}
    bool operator==(const point &b)const{return x==b.x&&y==b.y;}
    point operator -(const point &b)const{return point(x-b.x,y-b.y);}
    ll operator ^(const point &b)const{return (x*b.y-y*b.x);}
}p[maxn],stk[maxn];
int n;
int andrew(){
    sort(p+1,p+1+n);
    int len=2;stk[1]=p[1];stk[2]=p[2];
    for(int i=3;i<=n;i++){
        while(len>1 && ((stk[len]-stk[len-1])^(p[i]-stk[len-1]))>=0 )len--;
        stk[++len]=p[i];
    }int k=len;
    for(int i=n-1;i>=1;i--){
        while(len>k && ((stk[len]-stk[len-1])^(p[i]-stk[len-1]))>=0 )len--;
        stk[++len]=p[i];
    }return len;
}
bool cmp2(point a,point b){return atan2(a.y,a.x)<atan2(b.y,b.x);}
bool cmp3(point a,point b){return (a^b)>0;}
ll mj(point a,point b,point c){return abs((b-a)^(c-a));}
ll ok(point a,point b,point c,point d){
    ll abc=mj(a,b,c);
    ll acd=mj(a,c,d);
    ll abd=mj(a,b,d);
    ll bcd=mj(b,c,d);
    if(abc+acd>abd)return abc+acd;
    return min(abc+min(bcd,acd) ,bcd+acd );
}
ll dp1[maxn][maxn],dp2[maxn][maxn];
int main(){
    scanf("%d",&n);
    if(n<=3){puts("0 0");return 0;}
    for(int i=1;i<=n;i++)scanf("%lld%lld",&p[i].x,&p[i].y);
    ll A=0,B=9e18;
    int t=andrew()-1;
    if(t==3){
        ll aa=mj(stk[1],stk[2],stk[3]);
        for(int i=1;i<=n;i++){
            if(p[i]==stk[1]||p[i]==stk[2]||p[i]==stk[3])continue;
            ll aaa=0;
            aaa=max(aaa,aa-mj(stk[1],stk[2],p[i]));
            aaa=max(aaa,aa-mj(stk[1],stk[3],p[i]));
            aaa=max(aaa,aa-mj(stk[2],stk[3],p[i]));
            A=max(A,aaa);
        }goto ed;
    }for(int i=t+1;i<=2*t+1;i++)stk[i]=stk[i-t];
    for(int i=1;i<=2*t;i++){
        int j=i+1;if(j==2*t+1)j=1;
        int k=j+1;if(k==2*t+1)k=1;
        while(i!=k){
            while(j!=k&&((stk[k]-stk[i])^(stk[j]-stk[i])) < ((stk[k]-stk[i])^(stk[j+1]-stk[i]))){
                j++;if(j==2*t+1)j=1;
            }
            dp1[i][k]=max(dp1[i][k],mj(stk[i],stk[j],stk[k]));
            k++;if(k==2*t+1)k=1;
        }
    }
    for(int i=1;i<=t;i++){
        for(int j=i+1;j<=t;j++){
            A=max(A,dp1[i][j]+dp1[j][t+i]);
        }
    }
    ed:;
    point pp[maxn];
    for(int i=1;i<=n;i++){
        point mi=p[i];
        int cnt=0;
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            pp[++cnt]=p[j]-mi;
        }sort(pp+1,pp+1+cnt,cmp3);
        pp[cnt+1]=pp[1];pp[cnt+2]=pp[2];pp[cnt+3]=pp[3];pp[cnt+4]=pp[4];
        for(int j=1;j<=cnt;j++){
            for(int k=j+1;k<j+4&&k<cnt+5;k++){
                for(int l=k+1;l<k+4&&l<cnt+5;l++){
                    B=min(B,ok(point(0,0),pp[j],pp[k],pp[l]));
                }
            }
        }
    }
    cout<<B<<" "<<A<<endl;
    return 0;
}

5/19 upd：发现存在误差，已修改，不确定正确性。
直接上标程：

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 2e3 + 5;
const int mod = 1e9 + 7;
struct Point {
    int x, y;
    Point(int _x = 0, int _y = 0): x(_x), y(_y) {}
    Point operator + (const Point &b) const {return Point(x + b.x, y + b.y);}
    Point operator - (const Point &b) const {return Point(x - b.x, y - b.y);}
    LL operator * (const Point &b) const {return ((LL)x * b.x + (LL)y * b.y);}
    LL operator ^ (const Point &b) const {return ((LL)x * b.y - (LL)y * b.x);}
    bool operator < (const Point &b) const {
        if((x - b.x) == 0) return y < b.y;
        else return x < b.x;
    }
} p[maxn], w;
struct node {
    int u, v;
    bool operator <(const node &b) const {return ((p[u] - p[v]) ^ (p[b.u] - p[b.v])) > 0;}
};
vector<node> f;
int id[maxn];
int main() {
    int n, i, j, l, r;
    LL A = 0, B = 1LL << 60;
    scanf("%d", &n);
    for(i = 0; i < n; i++) scanf("%d%d", &p[i].x, &p[i].y);
    for(i = 0; i < n; i++) id[i] = i;
    sort(p, p + n);
    for(i = 0; i < n; i++) {
        for(j = i + 1; j < n; j++) f.push_back(node{i, j});
    }
    sort(f.begin(), f.end());
    for(auto e : f) {
        i = e.u;j = e.v;
        if(id[i] > id[j]) swap(i, j);
        w = p[id[i]] - p[id[j]];
        A = max(A, abs((p[0] - p[id[j]]) ^ w) + abs((p[n - 1] - p[id[j]]) ^ w));
        if(id[i] && id[j] + 1 < n)
            B = min(B, abs((p[id[i] - 1] - p[id[j]]) ^ w) + abs((p[id[j] + 1] - p[id[j]]) ^ w));
        swap(id[i], id[j]);
        swap(p[id[i]], p[id[j]]);
    }
    cout << B << " " << A << endl;
    return 0;
}