题解：P12816 [NERC 2021] Connect the Points

fish_love_cat · 2025-06-15 13:32:46 · 题解

怎么被奶龙题硬控了 1h /qd

按 x 排序，然后让前两个点先连上，注意要先移 x 再移 y。

第三个点直接向移 y 时形成的竖线作垂就行了，分三种情况，向上延长，向下延长和不用延长。

大力写就行了。

#include<bits/stdc++.h>
using namespace std;
struct cat{
    int a,b,c,d;
}ans[15];
int siz;
struct fish{
    int x,y;
}a[3];
bool cmp(fish x,fish y){
    if(x.x==y.x)return x.y<y.y;
    return x.x<y.x;
}
int main(){
    cin>>a[0].x>>a[0].y;
    cin>>a[1].x>>a[1].y;
    cin>>a[2].x>>a[2].y;
    sort(a,a+3,cmp);
    if(a[0].x!=a[1].x)
    ans[++siz]={a[0].x,a[0].y,a[1].x,a[0].y};
    if(a[0].y!=a[1].y)
    ans[++siz]={a[1].x,a[0].y,a[1].x,a[1].y};
    if(a[0].y>=a[2].y&&a[1].y<=a[2].y||a[0].y<=a[2].y&&a[1].y>=a[2].y){
        ans[++siz]={a[1].x,a[2].y,a[2].x,a[2].y};
    }else{
        int xx=siz;
        if(abs(ans[xx].a-a[2].x)+abs(ans[xx].b-a[2].y)>=
            abs(a[1].x-a[2].x)+abs(a[1].y-a[2].y)){
            if(a[1].x!=a[2].x)
            ans[++siz]={a[1].x,a[1].y,a[2].x,a[1].y};
            if(a[1].y!=a[2].y)
            ans[++siz]={a[2].x,a[1].y,a[2].x,a[2].y};
        }else{
            if(ans[xx].a!=a[2].x)
            ans[++siz]={ans[xx].a,ans[xx].b,a[2].x,ans[xx].b};
            if(ans[xx].b!=a[2].y)
            ans[++siz]={a[2].x,ans[xx].b,a[2].x,a[2].y};
        }
    }
    cout<<siz<<'\n';
    for(int i=1;i<=siz;i++)
        cout<<ans[i].a<<' '<<ans[i].b<<' '<<ans[i].c<<' '<<ans[i].d<<'\n';
    return 0;
}