TLE求调
  • 板块P1766 液体滴落
  • 楼主hnczy
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/1 17:36
  • 上次更新2024/8/1 18:59:54
查看原帖
TLE求调
991913
hnczy楼主2024/8/1 17:36
#include<bits/stdc++.h>
using namespace std;
struct node {
	int x1,x2,y1,y2;
	double k,b;
}a[100005];
int n,s,y=0x3f3f3f3f,yy,ii;
int main(){
	scanf("%d%d",&n,&s);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2 );
		a[i].k =(1.0*a[i].y1-a[i].y2)/(a[i].x1-a[i].x2);
		a[i].b =1.0*(a[i].y2*a[i].x1-a[i].y1*a[i].x2)/(a[i].x1-a[i].x2);
	}
	while(1){
		ii=0;
		yy=y;
		for(int i=1;i<=n;i++){
			if(s<max(a[i].x1 ,a[i].x2 )&&s>min(a[i].x1 ,a[i].x2 )&&((yy>s*a[i].k +a[i].b&&yy==y)||(yy!=y&&yy<s*a[i].k +a[i].b ))){//在线段范围内并且这个线段是最上面的 
				yy=s*a[i].k +a[i].b;
				ii=i;
			}
		}
		if(!ii){//并没有线段能接住水滴 
			printf("%d\n",s);
			exit(0);
		}
		else{//有线段能接住水滴 
			if(a[ii].y1 <a[ii].y2 ){
				y=a[ii].y1 ;
				s=a[ii].x1 ;
			}
			else {
				y=a[ii].y2 ;
				s=a[ii].x2 ;
			}
		}
	}
	
	return 0;
}

2024/8/1 17:36
加载中...