36分求调
查看原帖
36分求调
845394
MYXJWXR楼主2024/5/30 12:53
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005,E=1.25e7+5;
struct EDGE{
	int to,next;
}edge[E];
int n,m;
int head[MAXN],d[MAXN],cnt;
double k[MAXN],b[MAXN];
double x[MAXN],y[MAXN],kx[MAXN],ky[MAXN];
void add(int u,int v){
	d[v]++;
	cnt++;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void get(int idx,double x,double y,double kx,double ky){
	k[idx]=(ky-y)/(kx-x);
	b[idx]=y-k[idx]*x;
}
double dis(int idx,double x_){
	double y_=k[idx]*x_+b[idx];
	if(y[idx]==ky[idx]) return y[idx];
	if(x[idx]==kx[idx]) return min(y[idx],ky[idx]);
	return y_;
}
void repeat(int p,int q){
	if(x[p]>x[q]) swap(p,q);
	if(kx[p]<x[q]) 
	   return ;
	double y_=dis(p,x[q]);
	if(y_<min(y[q],ky[q])) add(p,q);
	else add(q,p);
}
queue<int> q;
void topo_sort(){
	for(int i=1;i<=n;i++)
		if(d[i]==0)
			q.push(i);
	while(!q.empty()){
		int root=q.front();
		cout<<root<<" ";
		q.pop();
		for(int i=head[root];i;i=edge[i].next){
			int t=edge[i].to;
			d[t]--;
			if(!d[t])
				q.push(t);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>kx[i]>>ky[i];
		if(x[i]>kx[i])
			swap(x[i],kx[i]),swap(y[i],ky[i]);
		get(i,x[i],y[i],kx[i],ky[i]);
		for(int j=1;j<i;j++)
			repeat(i,j);
	}
	topo_sort();
	return 0;
}
2024/5/30 12:53
加载中...