Gym101611J 未被三角形覆盖的点

题意：w*h的平面中，给出n个三角形，且三角形面积总和不超过w*h。求任意一个未被三角形覆盖的点。

w,h<=10000, n<=100000, 坐标均为整数。

首先因为面积覆盖不满，这样的点必然存在。但是这里n非常大，如果用常规计算几何方法仅计算线段相交已经O(n^2)级别，而且后续也十分复杂，并不可做。因此考虑一条竖直扫描线，以扫到三角形段的长度总和(重复算多次)得到一个函数y=f(x)。如果对斜率求前缀和，在线段端点处更新，容易在扫描中计算出任意位置的函数值。

显然该函数必有一点x0的处函数值比h小，所以在这个点未被覆盖满，必然有解。考虑如何找到这样的x0：一个重要的观察是，因为坐标均为整点，所以函数f(x)在(n,n+1)闭区间中必为线性的。于是(n,n+1)区间函数的面积<h等价于该区间中点值小于h。因此枚举中点就可以找到x0。

找到x0后就比较方便了。对x=x0位置处被三角形覆盖的竖直区间端点排序，找到未被覆盖的区间即可。

```
/*
```
```
Author: fffasttime
```
```
Date: 2019/09/21 13:10
```
```
 */
```
```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
typedef long long ll;
```
```
#define inc(i,n) for (int i=0;i<n;i++)
```
```
const int N=100010;
```
```
typedef double db;
```
```
db sk[N],sh[N];
```
```
const db eps=1e-12;
```
```
struct Line{
```
```
	db x1,y1,x2,y2; int t;
```
```
	db at(db x)const{
```
```
		return y1+(y2-y1)*((x-x1)/(x2-x1));
```
```
	}
```
```
}line[N<<2],li2[N<<2];
```
```
int linc;
```

void added(int x1, int y1, int x2, int y2){

```
		if (x1==x2) return;
```
```
		db k=(db)(y2-y1)/(x2-x1);
```
```
		sk[x1]-=k;
```
```
		sk[x2]+=k;
```
```
		sh[x1]-=y1;
```
```
		sh[x2]+=y2;
```
```
		if (x1<x2)
```
```
		line[linc++]={x1,y1,x2,y2,1};
```
```
		else
```
```
		line[linc++]={x2,y2,x1,y1,-1};
```
```
}
```
```
int main(){
```
```
	int n,w,h;
```
```
	cin>>n>>w>>h;
```
```
	for (int i=0;i<n;i++){
```
```
		int x1,y1,x2,y2,x3,y3;
```

		scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);

		if (x1*y2-x2*y1+x2*y3-x3*y2+x3*y1-x1*y3<0)

```
			swap(x2,x3), swap(y2,y3);
```
```
		added(x1,y1,x2,y2);
```
```
		added(x2,y2,x3,y3);
```
```
		added(x3,y3,x1,y1);
```
```
	}
```
```
	db ny=0,x0=0,ssy=0,ssk=0;
```
```
	for (int i=0;i<w;i++){
```
```
		x0=i+0.5;
```
```
		ssk+=sk[i];
```
```
		ny+=sh[i]+ssk*0.5;
```
```
		if (ny<h-1e-5){
```
```
			break;
```
```
		}
```
```
		ny+=ssk*0.5;
```
```
	}
```
```
	int scs=1; db lay=0, dif=0, ansy;
```
```
	linc=0;
```
```
	for (int i=0;i<3*n;i++)
```
```
		if (line[i].x1<x0 && line[i].x2>x0)
```
```
			li2[linc++]=line[i];	
```
```
	li2[linc++]={0,0,w,0,-1};
```
```
	li2[linc++]={w,h,0,h,1};
```

	sort(li2,li2+linc,[&](const Line &a, const Line &b){return a.at(x0)<b.at(x0);});

```
	for (int i=0;i<linc;i++){
```
```
		db y=li2[i].at(x0);
```
```
		if (scs==0 && y-lay>dif){
```
```
			dif=y-lay;
```
```
			ansy=(lay+y)/2;
```
```
		}
```
```
		scs+=li2[i].t;
```
```
		lay=y;
```
```
	}
```
```
	printf("%.9f %.9f\n",x0,ansy);
```
```
	return 0;
```
```
}
```

发表评论 取消回复

发表评论取消回复