2014
11-30

# Gunshots

President Bartlet was shot! A group of terrorists shot to the crowd when President Bartlet waved to cheering people after his address. Many people were shot by the irrational bullets. Senior FBI agent Don Epps takes responsibility for this case. According to a series of crime scene investigation, including analyzing shot shells, replaying video from closed-circle television and collecting testimony by witnesses, Don keeps all the information about where and how the terrorists shot to crowd, as well as the location of every single person when the gun shoot happened. Now he wants to know how many gunshot victims are there in this case.

Imagine that each target person can be regarded as a polygon (can be concave or self-intersecting) and each gunshot can be regarded as a half-line. The bullet will be stopped by the first person it shoots. A person can be shot in three ways:

To simplify the problem, we assume that any two polygons can be completely separated by a line. Also each start point of the gunshot can be separated from each polygon by a line. Now given M people and N gunshots, please work out which person has been shot by each bullet.

There are multiple test cases in the input. The first line of the input file is an integer T demonstrating the number of test cases. (T<=10).

For each test case, the first line is an integer N, representing the number of people (polygons). Following lines demonstrates the polygons. For the ith polygon (0<=i<N), the first line is an integer Qi, representing the number of edges of this polygon. In each of the following Qi lines, there are two real numbers xi and yi representing a point. Every pair of adjacent points demonstrate an edge of this polygon (i.e. (xi, yi) to (xi+1, yi+1) is an edge, in which 0<=i<Qi-1), and (xQi-1, yQi-1) to (x0, y0) also demonstrates an edge of this polygon.

Then there is a line contains an integer M representing the number of gunshots. In the following M lines, each line contains four real numbers x, y, dx and dy, representing the start point (x, y) and direction vector (dx, dy) of that gunshot.

In all test cases, we assume that 0< N<=100, 0<Qi<=1000, 0<M<=10000.

There are multiple test cases in the input. The first line of the input file is an integer T demonstrating the number of test cases. (T<=10).

For each test case, the first line is an integer N, representing the number of people (polygons). Following lines demonstrates the polygons. For the ith polygon (0<=i<N), the first line is an integer Qi, representing the number of edges of this polygon. In each of the following Qi lines, there are two real numbers xi and yi representing a point. Every pair of adjacent points demonstrate an edge of this polygon (i.e. (xi, yi) to (xi+1, yi+1) is an edge, in which 0<=i<Qi-1), and (xQi-1, yQi-1) to (x0, y0) also demonstrates an edge of this polygon.

Then there is a line contains an integer M representing the number of gunshots. In the following M lines, each line contains four real numbers x, y, dx and dy, representing the start point (x, y) and direction vector (dx, dy) of that gunshot.

In all test cases, we assume that 0< N<=100, 0<Qi<=1000, 0<M<=10000.

1
1
4
0 0
1 1
0 1
1 0
2
-1 0 1 0
-2 0 -1 0

HIT 0
MISS
*****

HintThe figure of the first case in the samples is as follows:


1.射击判断：这里利用旋转卡壳，用平行于枪的射线的平行线对卡住人的凸包，那么射线和对踵点对构成的线段相交就是射中的充要条件。

2.编程优化：如果对于每条射线枚举所有人寻找对踵点对一定会TLE，因此这里利用旋转卡壳计算是斜率的单调性优化。首先，将所有的射线的方向向量映射到(-90,90]区间上（因为凸包计算的斜率均在这个区间）。然后，对所有射线按斜率递增排序。最后，扫描所有的射线，扫描过程中，让卡住凸包的平行线随着射线的斜率旋转即可，每次旋转到刚好不小于射线斜率的时候，卡住的就是平行于射线的平行线对穿过的对踵点对。这里，我是采用先将所有的对踵点对找到存起来，最后用来查找，因为不这么做会TLE（可能是我的编程问题，常数太大了0
0）。总体的时间均摊后的代价是O(NM)。WA几次后发现凸包写得有问题，（重点 = =囧），看来改写份凸包的模板了。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

typedef struct pnode
{
double x,y,d;
pnode( double a, double b ) {x = a;y = b;}
pnode(){};
}point;
point P[ 105 ][ 1005 ];
point P0,Pn;
int   Q[ 105 ];
int   top[ 105 ];

typedef struct lnode
{
double x,y,dx,dy,d;
int    id,hit,sign;
lnode( point a, point b ) {x = a.x;y = a.y;dx = b.x-a.x;dy = b.y-a.y;}
lnode(){};
}line;
line L[ 10005 ];

typedef struct knode
{
int   size;
line  l[ 1005 ];
point a[ 1005 ];
point b[ 1005 ];
}slope;
slope S[ 105 ];

//两点间距离
double dist( point a, point b )
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

//点到直线距离
double dist( point a, line l )
{
return fabs(l.dx*(a.y-l.y)-l.dy*(a.x-l.x))/sqrt(l.dx*l.dx+l.dy*l.dy);
}

//叉乘 ab*ac
double crossproduct( point a, point b, point c )
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

//返回点a:(x,y)在直线l:(x0+tdx,y0+tdy)的参数t
double parameter( line l, point a )
{
if ( l.dx ) return (a.x-l.x)/l.dx*l.sign;
else return (a.y-l.y)/l.dy*l.sign;
}

//直线相交判断
bool l_cross_l( line a, line b )
{
double t1 = b.dx*(a.y-b.y)-b.dy*(a.x-b.x);
double t2 = b.dx*(a.y+a.dy-b.y)-b.dy*(a.x+a.dx-b.x);
return t1*t2 <= 0;
}

//两直线交点
point crosspoint( line l, point a, point b )
{
line m = line( a, b );
if ( m.dx*l.dy == m.dy*l.dx ) {
if ( dist( point( l.x, l.y ), a ) < dist( point( l.x, l.y ), b ) )
return a;
else return b;
}else {
double a1 = -l.dy,b1 = l.dx,c1 = l.dx*l.y-l.dy*l.x;
double a2 = -m.dy,b2 = m.dx,c2 = m.dx*m.y-m.dy*m.x;
double x = (c1*b2-c2*b1)/(a1*b2-a2*b1);
double y = (c1*a2-c2*a1)/(b1*a2-b2*a1);
return point( x, y );
}
}

//两向量的夹角余弦
double angle( line a, line b )
{
return (a.dx*b.dx+a.dy*b.dy)/sqrt(a.dx*a.dx+a.dy*a.dy)/sqrt(b.dx*b.dx+b.dy*b.dy);
}

//点排序
bool cmp1( point a, point b )
{
if ( a.x == b.x ) return a.y < b.y;
else return a.x < b.x;
}

//级角排序
bool cmp2( point a, point b )
{
double cp = crossproduct( P0, a, b );
if ( cp == 0 ) return a.d < b.d;
else return cp > 0;
}

//直线斜率排序
bool cmp3( line a, line b )
{
return a.dy*b.dx < b.dy*a.dx;
}

//直线编号排序
bool cmp4( line a, line b )
{
return a.id < b.id;
}

//凸包扫描算法
void Graham( int N, int M )
{
point  *p,q;
double  d1,d2,a1,a2;
for ( int i = 0 ; i < N ; ++ i ) {
p = &P[i][0];
sort( p+0, p+Q[i], cmp1 );
P0 = p[0];
for ( int j = 1 ; j < Q[i] ; ++ j )
p[j].d = dist( P0, p[j] );
sort( p+1, p+Q[i], cmp2 );

//计算凸包
if ( Q[i] > 2 ) {
int top = 2;
for ( int j = 3 ; j < Q[i] ; ++ j ) {
while ( top > 0 && crossproduct( p[top-1], p[top], p[j] ) <= 0 ) -- top;
p[++ top] = p[j];
}
p[++ top] = p[0];
//删掉共线的中间点
int now = 1;
for ( int j = 2 ; j <= top ; ++ j )
if ( crossproduct( p[now-1], p[now], p[j] ) == 0 ) p[now] = p[j];
else p[++ now] = p[j];
Q[i] = now;
}

//计算初始点对
int L1 = 0,L2 = 0;
if ( Q[i] > 1 ) L2 = 1;
for ( int j = 1 ; j < Q[i] ; ++ j )
if ( p[j].x > p[(j+1)%Q[i]].x ) {
L2 = j;break;
}
int Ln = L2;
//旋转卡壳，记录斜率和对踵点对
line lt = line( point(0,0), point(0,-1) );
S[i].size = -1;
while ( p[L1].x <= p[(L1+1)%Q[i]].x || p[L2].x >= p[(L2+1)%Q[i]].x ) {
a1 = angle( lt, line( p[L1], p[(L1+1)%Q[i]] ) );
a2 = angle( lt, line( p[(L2+1)%Q[i]], p[L2] ) );
S[i].size ++;
S[i].a[S[i].size] = p[L1];
S[i].b[S[i].size] = p[L2];
if ( a1 > a2 && p[L1].x <= p[(L1+1)%Q[i]].x ) {
lt = line( p[L1], p[(L1+1)%Q[i]] );
L1 = (L1+1)%Q[i];
}else {
lt = line( p[(L2+1)%Q[i]], p[L2] );
L2 = (L2+1)%Q[i];
}
S[i].l[S[i].size] = lt;
}
S[i].size ++;
S[i].a[S[i].size] = p[0];
S[i].b[S[i].size] = p[Ln];
S[i].l[S[i].size] = line( point(0,0), point(0,1) );
}
int now[101];
for ( int i = 0 ; i < N ; ++ i )
now[i] = 0;

sort( L, L+M , cmp3 );
for ( int i = 0 ; i < M ; ++ i ) {
L[i].hit = -1;
for ( int j = 0 ; j < N ; ++ j ) {
while ( cmp3( S[j].l[now[j]], L[i] ) ) ++ now[j];
//相交判断
if ( l_cross_l( line( S[j].a[now[j]], S[j].b[now[j]] ), L[i] ) ) {
q  = crosspoint( L[i], S[j].a[now[j]], S[j].b[now[j]] );
d2 = dist( q, point( L[i].x, L[i].y ) );
//交点在射线的相反方向上
if ( parameter( L[i], q ) < 0 ) continue;
//否则取与射线原点最近的交点
if ( L[i].hit == -1 ) {
L[i].hit = j;
L[i].d = d2;
}else if ( L[i].d > d2 ) {
L[i].hit = j;
L[i].d = d2;
}
}
}
}

sort( L, L+M, cmp4 );
for ( int i = 0 ; i < M ; ++ i )
if ( L[i].hit != -1 )
printf("HIT %d\n",L[i].hit);
else printf("MISS\n");
}

int main()
{
int T,N,M;
while ( scanf("%d",&T) != EOF )
while ( T -- ) {
scanf("%d",&N);
for ( int i = 0 ; i < N ; ++ i ) {
scanf("%d",&Q[i]);
for ( int j = 0 ; j < Q[i] ; ++ j )
scanf("%lf%lf",&P[i][j].x,&P[i][j].y);
}
scanf("%d",&M);
for ( int i = 0 ; i < M ; ++ i ) {
scanf("%lf%lf%lf%lf",&L[i].x,&L[i].y,&L[i].dx,&L[i].dy);
L[i].id = i;
if ( L[i].dx < 0 ) {//转化区间
L[i].dx *= -1;
L[i].dy *= -1;
L[i].sign = -1;
}else L[i].sign = 1;
}
Graham( N, M );
printf("*****\n");
}
return 0;
}


1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。

2. “可以发现,树将是满二叉树,”这句话不对吧，构造的树应该是“完全二叉树”，而非“满二叉树”。