【BZOJ1074】【SCOI2007】折纸origami

  计算几何，大概就是把纸倒着折回原来的形状，把它们在原图中的可能的位置全部找出来，判断是否在正方形区域内，就好了。

  每次对一个点翻折时需要判断一下这个点是否在有向线段的逆时针方向上，如果不在那么这个点是不可行的。

  有没有可能一个点是不可行的，但是由它翻折得到的点是可行的呢？显然不可能，因为翻折回来的那部分面积的范围是小于翻折前那整块的范围的。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010;
const double eps=1e-6;

struct Line
{
	double px,py,vx,vy;
	Line (double _px=0,double _py=0,double _vx=0,double _vy=0):px(_px),py(_py),vx(_vx),vy(_vy){}
}L[10];

double Det(double ux,double uy,double vx,double vy) {return ux*vy-uy*vx;}
double Dot(double ux,double uy,double vx,double vy) {return ux*vx+uy*vy;}
double length(const double &a,const double &b) {return sqrt(a*a+b*b);}
void VecRot(double &ax,double &ay,const Line &b)
{
	double ux=ax-b.px,uy=ay-b.py,vx=b.vx,vy=b.vy;
	double vcos=Dot(ux,uy,vx,vy)/(length(ux,uy)*length(vx,vy));
	double ccos=2*vcos*vcos-1,csin=2*vcos*sqrt(1-vcos*vcos);
	ax=Dot(ux,uy,ccos,csin)+b.px,ay=Det(ccos,csin,ux,uy)+b.py;
}

int cmp(double ux,double uy) {if (fabs(ux-uy)<eps) return 0;if (ux<uy) return -1;else return 1;}

int top,tail;
int n,m;

int DFS(double x,double y,int o)
{
	if (o==0) if (cmp(x,100)<0 && cmp(x,0)>0 && cmp(y,100)<0 && cmp(y,0)>0) return 1;else return 0;
	if (cmp(Det(x-L[o].px,y-L[o].py,L[o].vx,L[o].vy),0)>=0) return 0;
	double tx=x,ty=y;
	VecRot(tx,ty,L[o]);
	return DFS(x,y,o-1)+DFS(tx,ty,o-1);
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lf%lf%lf%lf",&L[i].px,&L[i].py,&L[i].vx,&L[i].vy),L[i].vx-=L[i].px,L[i].vy-=L[i].py;
	scanf("%d",&m);
	for (int t=1;t<=m;t++)
	{
		double lx,ly;
		scanf("%lf%lf",&lx,&ly);
		printf("%d\n",DFS(lx,ly,n));
	}
	return 0;
}