90pts 求助
  • 板块灌水区
  • 楼主_zuoqingyuan
  • 当前回复1
  • 已保存回复2
  • 发布时间2023/10/28 22:52
  • 上次更新2023/10/29 09:32:14
查看原帖
90pts 求助
731650
_zuoqingyuan楼主2023/10/28 22:52
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct node{
    int xa,xb,ya,yb,f1,f2;double k,b;//f1为是横的木棍,f2为竖的木棒
}a[5005];
vector<int> v[5005];
int n,x1,x2,y1,y2,d[5005];
bool pd(node a,node b,int i,int j){//a是否在b下
    if(a.xb<b.xa)return 0;
    else{
        double x=max(a.xa,b.xa),ya,yb;
        if(a.f2)ya=a.ya;
        else ya=x*a.k+a.b;
        if(b.f2)yb=b.ya;
        else yb=x*b.k+b.b;
        //printf("sssss%d->%d x:%.2lf ya:%.2lf  yb:%.2lf xa:%d xb:%d\n",i,j,x,ya,yb,a.xb,b.xa);
        if(ya<yb)return 1;
        else return 0;
    }
}
void topsort(){
    queue<int> q;
    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=0;i<v[t].size();i++){
            int y=v[t][i];
            d[y]--;
            if(d[y]==0){
                cout<<y<<" ";
                q.push(y);
            }
        }
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d %d %d %d",&a[i].xa,&a[i].ya,&a[i].xb,&a[i].yb)
        if(a[i].xa>a[i].xb)swap(a[i].xa,a[i].xb),swap(a[i].ya,a[i].yb);
        if(a[i].xa==a[i].xb)a[i].f2=1;
        else{
            a[i].k=(a[i].yb-a[i].ya)*1.0/(a[i].xb-a[i].xa)*1.0;
            a[i].b=(double)a[i].ya*1.0-a[i].k*(a[i].xa*1.0);
        }
        //cout<<a[i].f1<<" "<<a[i].f2<<" "<<a[i].k<<" "<<a[i].b<<" "<<a[i].xb<<endl;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)continue;
            if(pd(a[i],a[j],i,j)){
                d[j]++;
                v[i].push_back(j);
            }
        }
    }
    /*for(int i=1;i<=n;i++){
    cout<<"sss"<<i<<" ";
        for(int j=0;j<v[i].size();j++){
            cout<<v[i][j]<<" ";
        }
        cout<<endl;
    }*/
    topsort();
    return 0;
} 

90pts,WA#3,#12。求调

2023/10/28 22:52
加载中...