P7860-题解

· · 题解

题面：

这里

分析：

假定要使某根木棍向下移动，且不碰到其他木棍，那我们要使得这根木棍下其他木棍比他先移动。

我们可以在此基础上建立一个有向图：如果木棍 i 需要在木棍 j 前移动，就连一条 i 到 j 的边。样例 1 就是这样的。

最后的答案就是这个图的拓扑序

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct node{
    int x1,x2,y1,y2;
}a[5005];//存储木棍的信息
queue<int> q;
const int N=5005*5005/2;
int n,d[5005],ver[5005],to[N],nxt[N],idx;
void add(int x,int y){
    to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx;
}
int pd(node u,node v){  //判断木棒的相对位置，最核心的代码
    int f=1;        
    if(u.x1>v.x1) swap(u,v),f=-f;   
    if(u.x2<v.x1) return 0; 
    double k,B,yy;
    if(!(u.x2-u.x1)){
        k=1.0*(v.y2-v.y1)/(v.x2-v.x1);
        B=(double)v.y1-k*v.x1;
        yy=k*u.x1+B;
        if(u.y1>yy) return f;
        return -f;
    }
    k=1.0*(u.y2-u.y1)/(u.x2-u.x1);
    B=(double)u.y1-k*u.x1;
    yy=k*v.x1+B;   
    if(yy>v.y1) return f;
    return -f;
}
void topsort(){//拓扑排序板子
    for(int i=1;i<=n;i++){
        if(!d[i]){
            cout<<i<<" ";
            q.push(i);
        }
    }
    while(q.size()){
        int t=q.front();q.pop();
        for(int i=ver[t];i;i=nxt[i]){
            int tp=to[i];
            d[tp]--;
            if(d[tp]==0){
                cout<<tp<<" ";
                q.push(tp);
            }
        }
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d %d %d %d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
        if(a[i].x1>a[i].x2)swap(a[i].x1,a[i].x2),swap(a[i].y1,a[i].y2);//让两个端点有先后顺序
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            int p=pd(a[i],a[j]);
            if(p==1)add(j,i),d[i]++;
            if(p==-1)add(i,j),d[j]++;//建图
        }
    }
    topsort();
    return 0;
}

如有错误，请指出。