P5428 [USACO19OPEN]Cow Steeplechase II S

题目

$\bullet$ 给定$n$条线段，问去掉哪条线段使得剩下的线段没有交点，多种答案输出编号最小的一条，保证有解

前置知识：判定线段是否相交

$\bullet$ 将线段表示为函数形式，带公式求交点，判断交点是否在两条直线上，会爆精度

$\bullet$ 使用快速排斥实验 + 跨立实验（说白了就是向量）

    $\circ$ 快速排斥实验：

        $\diamond$ 快速排斥实验即初步判定两线段是否相交，将线段看做两个矩形的对角线判断两矩形是否相交

        $\diamond$ 快速排斥实验不能判定线段是否相交，还需进行跨立实验

    $\circ$ 跨立实验：

        $\diamond$ 跨立实验即判断两条线段是否互相跨立（互相跨越，即相交）

        $\diamond$ 由图可知，当两线段互相跨立时，从线段$x$的起点$A$出发向线段$y$的起点$C$和终点$D$构造向量$\overrightarrow{AC}，\overrightarrow{AD}$，显然$\overrightarrow{AC}，\overrightarrow{AD}$应该分别在线段$x$的两侧，对线段$y$同理。只要两线段中有一条不满足则两线段不相交。

        $\diamond$ 对与如何判断两向量是否在另一个向量的两侧，可以使用向量的叉乘。即同一方向的叉积正负性一样，所以对两向量分别与另一向量求叉积，若线段相交，那么两个叉积的积应该为正

分析

$\bullet$ 因为只要移除一条线段，这张地图就可以恢复到预期没有相交线段的状态，所以只要找出任意两条相交的线段，答案就是两条之一，暴力检查一下即可。于是转化为如何快速找到两条相交的线段

$\bullet$ 注意到两条线段相交的先决条件是这两条线段在x轴上的投影有交集

$\bullet$ 定义一个$set$来维护在$x$轴的投影上包含了$now$这个点的不相交线段 $\bullet$ 因为在$set$中线段不相交，所以线段的上下关系不会改变，可以用某条直线与线段交点的高度对线段排序

算法流程

$\bullet$ 对于输入的$2n$个点, 以$x$为第一关键字, $y$为第二关键字, 从小到大排序，并标记好该点属于哪一条线段

$\bullet$ 依次扫描每个点，设该点所在的线段为$seg$，这个点所在的$x$轴即为上面说的那条直线

    $\circ$ 若$seg$不在$set$内：二分找到$seg$应该插入的位置，并判断该位置上下的线段是否与$seg$相交。若相交，保存两条相交的线段下标并退出。否则，将$seg$加入$set$

    $\circ$ 若$seg$在$set$内：如果$seg$上下都有线段，找到这两条线段，判断它们是否相交。若相交，保存两条线段下标并退出。否则，将$seg$从$set$中删除 $\diamond$ 为什么在删除的时候需要再判断一次？ 因为在加入的时候之判断了新加入的线段与上下的关系，而并没有判断上下之间的关系，如下图

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<set>
using namespace std;

typedef long long ll;
#define it set<segment>::iterator
const int MAXN = 1e5+5;

template <typename T>
inline void read(T&x){
	x=0; char temp=getchar(); bool f=false;
	while(!isdigit(temp)){if(temp=='-') f=true; temp=getchar();}
	while(isdigit(temp)){x=(x<<1)+(x<<3)+temp-'0'; temp=getchar();}
	if(f) x=-x;
}
template <typename T>
void print(T x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+'0');
}

//basic
int n;

//Point
int cnt;
struct point{
	ll x,y;
	int belong;
	inline bool operator <(const point &a)const{return x!=a.x? x<a.x:y<a.y;}
	inline point operator -(const point &a){return (point){x-a.x,y-a.y};}
}p[MAXN<<1];

//Segment
ll now;
struct segment{
	point l,r;
	int tag;
	inline double calc()const{if(l.x==r.x) return l.y; return 1.0*l.y+1.0*(r.y-l.y)*1.0*(now-l.x)/(1.0*(r.x-l.x));}//计算当前线段（看做函数）在now处的取值，注意特判与x轴垂直的情况
	inline bool operator <(const segment &a)const{return calc()<a.calc();}
}l[MAXN];
set<segment> s;

inline ll CrossMul(point a,point b,point c){a=a-c,b=b-c; ll res=a.x*b.y-a.y*b.x; return res==0? 0:res>0? 1:-1;}

inline bool Cross(segment a,segment b){
	if(!(min(a.l.x,a.r.x)<max(b.l.x,b.r.x)&&min(b.l.x,b.r.x)<max(a.l.x,a.r.x)&&min(a.l.y,a.r.y)<max(b.l.y,b.r.y)&&min(b.l.y,b.r.y)<max(a.l.y,a.r.y))) return false;//快速排斥实验
	return CrossMul(b.l,a.r,a.l)*CrossMul(a.r,b.r,a.l)>0&&CrossMul(a.l,b.l,b.r)*CrossMul(b.l,a.r,b.r)>0;//跨立实验
}

int main(){
	read(n);
	for(register int i=1;i<=n;i++){
		ll x1,y1,x2,y2; read(x1),read(y1),read(x2),read(y2);
		p[++cnt]=(point){x1,y1,i},p[++cnt]=(point){x2,y2,i};
		l[i]=(segment){p[cnt-1],p[cnt],i};
	}
	sort(p+1,p+cnt+1);
	
	int first=0,second=0;//任意两条相交的线段编号
	for(register int i=1;i<=cnt;i++){//依次扫描每个点
		now=p[i].x;//更新now以便重载小于
		int id=p[i].belong;
		it seg=s.find(l[id]);
		if(seg!=s.end()){
			it pre=seg,next=seg; next++;
			if(pre!=s.begin()&&next!=s.end()){//找到seg的上线两条线段pre与next
				pre--;
				if(Cross(*pre,*next)){first=pre->tag,second=next->tag; break;}//上下相交了，退出
			}
			s.erase(seg);
		}
		else{
			it pos=s.lower_bound(l[id]);
			if(pos!=s.end()&&Cross(*pos,l[id])){first=pos->tag,second=id; break;}//当前与后一条相交了，退出
			if(pos!=s.begin()){
				pos--;
				if(Cross(*pos,l[id])){first=pos->tag,second=id; break;}//当前与前一条相交了，退出
			}
			s.insert(l[id]);
		}
	}
	
	if(first>second) swap(first,second);
	int temp=0;
	for(register int i=1;i<=n;i++)
		if(i!=second&&Cross(l[i],l[second])) temp++;
	print(temp>1? second:first);
	return 0;
}