zoj1866.cpp

最近在acm.zju.edu.cn上通过的题目的代码

#include <stdio.h>
#include <math.h>

const double eps=1e-6;

int dblcmp(const double &a,const double &b)
{
	if (fabs(a-b)<eps) return 0;
	if (a<b) return -1;
	return 1;
}

struct Point
{
	double x,y;
};

double det(const double &ax,const double &ay,const double &bx,const double &by)
{
	return ax*by-bx*ay;
}

double cross(const Point &a,const Point &b,const Point &c)
{
	return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}

double dotdet(const double &ax,const double &ay,const double &bx,const double &by)
{
	return ax*bx+ay*by;
}

double dot(const Point &a,const Point &b,const Point &c)
{
	return dotdet(a.x-b.x,a.y-b.y,a.x-c.x,a.y-c.y);
}

double dis(const Point &a,const Point &b)
{
	return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}

const Point zero={0.0,0.0};

void getpast(const Point &a,const Point &b,const Point &c,Point &d)
{
	double dd=sqrt(dis(b,c));
	Point ta,tb,tc;
	ta.x=a.x-b.x;
	ta.y=a.y-b.y;
	tb.x=(c.x-b.x)/dd;
	tb.y=(c.y-b.y)/dd;
	double dt=dot(zero,ta,tb);
	tb.x=tb.x*dt;
	tb.y=tb.y*dt;
	tc.x=tb.x-ta.x;
	tc.y=tb.y-ta.y;
	d.x=tc.x*2+a.x;
	d.y=tc.y*2+a.y;
	//printf("%lf %lf %lf %lf %lf %lf %lf %lf\n",a.x,a.y,b.x,b.y,c.x,c.y,d.x,d.y);
}

Point last[1010],curr[1010];
int ln,cn;
Point pa[1010],pb[1010];
int n;

void input()
{
	
}

int calc(const Point &des)
{
	cn=1;
	curr[0]=des;
	int i,j;
	double ts;
	for (i=n;i;)
	{
		--i;
		for (j=0;j<cn;++j)
			last[j]=curr[j];
		ln=cn;
		cn=0;
		for (j=0;j<ln;++j)
		{
			ts=cross(pa[i],pb[i],last[j]);
			//printf("%d %lf\n",j,ts);
			if (dblcmp(ts,0)==0) ;//curr[cn++]=last[j];
			else if (dblcmp(ts,0)>0)
			{
				curr[cn++]=last[j];
				getpast(last[j],pa[i],pb[i],curr[cn]);
				++cn;
			}
		}
	}
	int ans=0;
	for (i=0;i<cn;++i)
		if (dblcmp(curr[i].x,0)>0&&dblcmp(curr[i].x,100)<0&&dblcmp(curr[i].y,0)>0&&dblcmp(curr[i].y,100)<0) ++ans;
	return ans;
}

int main()
{
	int m,i;
	Point des;
	bool first = true;
    while (scanf("%d",&n) != EOF){
    if (first) first = false; else puts("");
	for (int i=0;i<n;++i)
		scanf("%lf %lf %lf %lf",&pa[i].x,&pa[i].y,&pb[i].x,&pb[i].y);
	scanf("%d",&m);
	for (int i=0;i<m;++i)
	{
		scanf("%lf %lf",&des.x,&des.y);
		printf("%d\n",calc(des));
	}
    }
	return 0;
}