题解：P6948 [ICPC 2018 WF] Single Cut of Failure

LastKismet · 2025-03-31 13:49:18 · 题解

发现古早写过这题，于是补一发题解。

思路

首先一个性质是两条对角线必然可行，所以只需要考虑特判一条线行不行即可。

那么这就是个经典问题：对于一条直线上的一些区间，希望你构造一个连续区间，使你构造的区间中包含给出所有区间的一个端点。

如何把原问题转化成这个经典问题呢？把这个框从一个顶点处断开然后展开成直线即可。类似于破环成链。

那么考虑双指针解决这个问题即可。实现细节见代码。

古早代码

#include<bits/stdc++.h>
using namespace std;

typedef pair<double,double> pdd;
typedef pair<int,int> pii;

const int N=1e6+5;

int n;
int w,h;
int ans;

struct dot{
    int loc,id;
}ds[N*2];
int nums[N];

inline int get_loc(int x,int y){
    if(y==0)return x;
    if(x==w)return y+w;
    if(y==h)return w+h+w-x;
    if(x==0)return w+h+w+h-y;
}

inline pdd ret_loc(int x){
    if(x<=w)return {x-0.1,0};
    if(x<=h+w)return {w,x-w-0.1};
    if(x<=w+h+w)return {w-(x-w-h-0.1),h};
    if(x<=h+w+h+w)return {0,h-(x-w-h-w-0.1)};
}

inline void print(double a,double b,double c,double d){
    printf("%lf %lf %lf %lf\n",a,b,c,d);
}

inline void ed(){
    cout<<2<<endl;
    print(0,0.1,w,h-0.1);
    print(0,h-0.1,w,0.1);
}

bool cmp(dot a,dot b){
    return a.loc<b.loc;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>w>>h;
    for(int i=1;i<=n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        ds[i*2-1].id=i;
        ds[i*2-1].loc=get_loc(a,b);
        ds[i*2].id=i;
        ds[i*2].loc=get_loc(c,d);
    }
    sort(ds+1,ds+1+n*2,cmp);
    for(int i=1,j=1;i<=n*2;i++){
        nums[ds[i].id]++;
        if(nums[ds[i].id]==2){
            double a=ds[j].loc,b=ds[i].loc;
            pdd res1=ret_loc(a),res2=ret_loc(b);
            if(ans==n){
                cout<<1<<endl;
                print(res1.first,res1.second,res2.first,res2.second);
                return 0;
            }
            while(nums[ds[i].id]==2){
                nums[ds[j].id]--;
                ans--;
                j++;
            }
        }
        ans++;
    }
    ed();
    return 0;
}