Pick-up sticks
Description
Stan has n sticks of various length. He throws them one at a time on the floor in a random way. After finishing throwing, Stan tries to find the top sticks, that is these sticks such that there is no stick on top of them. Stan has noticed that the last thrown stick is always on top but he wants to know all the sticks that are on top. Stan sticks are very, very thin such that their thickness can be neglected.
Input
Input consists of a number of cases. The data for each case start with 1 <= n <= 100000, the number of sticks for this case. The following n lines contain four numbers each, these numbers are the planar coordinates of the endpoints of one stick. The sticks are listed in the order in which Stan has thrown them. You may assume that there are no more than 1000 top sticks. The input is ended by the case with n=0. This case should not be processed.
Output
For each input case, print one line of output listing the top sticks in the format given in the sample. The top sticks should be listed in order in which they were thrown.
The picture to the right below illustrates the first case from input.
The picture to the right below illustrates the first case from input.
Sample Input
5 1 1 4 2 2 3 3 1 1 -2.0 8 4 1 4 8 2 3 3 6 -2.0 3 0 0 1 1 1 0 2 1 2 0 3 1 0
Sample Output
Top sticks: 2, 4, 5. Top sticks: 1, 2, 3.
Hint
Huge input,scanf is recommended.
Source
题目大意：按输入顺序在平面内落下N根木棍，要求输出最上方（即无木棍覆盖于其上）的木棍编号。
题目给出多组数据，N=0时结束
对于每根木棍暴力枚举其后放下的木棍，判断两线段是否相交
若某一木棍后无其他木棍与其相交，则输出其编号
对于判断两线段是否相交，有两种方法
法一：对于两条线段，先判断一它们为对角线的矩形是否有重叠
（若无重叠，则这两线段定不相交）
叉积判断两线段是否相交
法二：先用叉积判断两线相交或共线
对于共线的情况，用点积判断两线段是否有重合部分
（若点积的值为负，则两线段重合）
需要注意的是，
判断叉积时，需要满足两线段的端点均在另一线段的不同方向（判两次）
用点积判断共线线段是否相交时，也需判两次。。。。
#include<cstdio>
#include<iostream>
using namespace std;
int n;
struct point{
double x,y;
point(double a=0,double b=0){
x=a;y=b;
}
};
struct segment{
point a,b;
segment(point x=point(0,0),point y=point(0,0)){
a=x;b=y;
}
}l[100001];
bool f1(const segment &a,const segment &b){
if (min(a.a.x,a.b.x)>max(b.a.x,b.b.x))return 0;
if (max(a.a.x,a.b.x)<min(b.a.x,b.b.x))return 0;
if (min(a.a.y,a.b.y)>max(b.a.y,b.b.y))return 0;
if (max(a.a.y,a.b.y)<min(b.a.y,b.b.y))return 0;
return 1;
}
double xc(const point &o,const point &p1,const point &p2){
return (p1.x-o.x)*(p2.y-o.y)-(p2.x-o.x)*(p1.y-o.y);
}
bool f2(const segment &a,const segment &b){
if (xc(a.a,a.b,b.a)*xc(a.a,b.b,a.b)>=0)
if (xc(b.a,b.b,a.a)*xc(b.a,a.b,b.b)>=0)
return 1;
return 0;
}
bool check(const segment &a,const segment &b){
if (!f1(a,b))return 0;
if (!f2(a,b))return 0;
return 1;
}
int main(){
for (;;){
scanf("%d",&n);
for (int i=1;i<=n;++i){
double x1,x2,x3,x4;
scanf("%lf%lf%lf%lf",&x1,&x2,&x3,&x4);
l[i]=segment(point(x1,x2),point(x3,x4));
}
if (!n)break;
printf("Top sticks:");
int tot=0;
for (int i=1;i<=n;++i){
int f=1;
for (int j=i+1;j<=n;++j)
if (check(l[i],l[j])){
f=0;
break;
}
if (f){
if (tot)printf(",");
printf(" %d",i);
++tot;
}
}
printf(".\n");
}
}
#include<cstdio>
const int MaxN=100010;
int N;
struct point{
double x,y;
point(double a=0,double b=0){
x=a; y=b;
}
point operator - (const point &b) const{
point c;
c.x=x-b.x;
c.y=y-b.y;
return c;
}
double operator * (const point &b) const{
return x*b.y-b.x*y;
}
double operator ^ (const point &b) const{
return x*y+b.x*b.y;
}
};
struct segment{
point a,b;
}L[MaxN];
bool intersect(const segment &a,const segment &b){
double r1=((a.b-a.a)*(b.a-a.a))*((a.b-a.a)*(b.b-a.a));
double r2=((b.b-b.a)*(a.a-b.a))*((b.b-b.a)*(a.b-b.a));
if (r1<0&&r2<=0) return true;
if (r1<=0&&r2<0) return true;
if (!r1 && !r2){
if (((b.a-a.a)^(b.b-a.a))<0) return true;
if (((b.a-a.b)^(b.b-a.b))<0) return true;
}
return false;
}
int main(){
for (;;){
scanf("%d",&N);
if (!N) break;
for (int i=1;i<=N;++i)
scanf("%lf%lf%lf%lf",&L[i].a.x,&L[i].a.y,&L[i].b.x,&L[i].b.y);
printf("Top sticks:");
int s=0;
for (int i=1;i<=N;++i){
bool f=true;
for (int j=i+1;j<=N;++j)
if (intersect(L[i],L[j])){
f=false;
break;
}
if (f){
if (s) printf(",");
++s;
printf(" %d",i);
}
}
printf(".\n");
}
}
评论 (0)
