求助
查看原帖
求助
438957
retep楼主2022/11/2 11:52

思路是枚举所有的交点,按时间顺序排序,再处理哪些是真正的交点。

代码姑且不看指责的连贯性,就连是否被指责都是不对的,求hack小数据。

#include<bits/stdc++.h>
#define N 1005
#define ll long long
using namespace std;

int n,x[N],y[N],ans[N];
char dir[N];
bool del[N];

int cnt,fa[N];
struct node{
	int a,b,t;
	bool operator <(node other)const{
		return t<other.t;
	}
}e[N*N];

void add(int u,int k){
	ans[u]+=k;
	if(fa[u]!=u)add(fa[u],k);
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>dir[i]>>x[i]>>y[i],fa[i]=i;
	for(int i=1;i<=n;i++)
		if(dir[i]=='N')
			for(int j=1;j<=n;j++)
				if(dir[j]=='E'&&x[i]>=x[j]&&y[i]<=y[j])
					if(x[i]-x[j]<y[j]-y[i])e[++cnt]={i,j,y[j]-y[i]};
					else if(x[i]-x[j]>y[j]-y[i])e[++cnt]={j,i,x[i]-x[j]};
	sort(e+1,e+cnt+1);
	for(int i=1;i<=cnt;i++){
		if(!del[e[i].a]&&!del[e[i].b]){
			del[e[i].a]=true;
			ans[e[i].b]++;
			cout<<e[i].a<<"指责"<<e[i].b<<endl;
			// fa[e[i].a]=e[i].b;
			// add(e[i].b,ans[e[i].a]+1);
		}
	}
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
	return 0;
}
2022/11/2 11:52
加载中...