首页 > 其他 > 详细

POJ 3304

时间:2014-07-24 21:38:32      阅读:320      评论:0      收藏:0      [点我收藏+]

题目可以转化成是否存在这样的一条直线,穿过所有的线段。这是很容易就能想到的。

然后,假如只有一个端点重合,那么我们可以知道,必定会有属于两条线段的某两个端点连出的直线可以穿过所有线段。这是枚举的思想。

那么,我们该怎么判定直线与线段有交点呢?不妨通过跨立的定义来做,这是经人点醒了才想到的。

在求线段是否有交点的时候用到过跨立,但我认为,跨立的定义应该是延长的线后是否存在交点(当前包括开始就存在交点的。)

假设枚举两点得到的线段是A1A2,判断是否有交点的线段是B1B2,则要求A1A2跨立B1B2。

设P1=向量(O->B1),P2=(O->B2),Q1=(O->A1),Q2=(O->A2);

则((P1-Q1)x(Q2-Q1))*((Q1-P2)x(Q2-Q1))>=0

bubuko.com,布布扣
 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <math.h>
 6 #define eps 0.00000001
 7 using namespace std;
 8 
 9 typedef struct po{
10     double x,y;
11 }Point;
12 
13 typedef struct pl{
14     Point start,end;
15 }Pleg;
16 int how_point,how_pleg;
17 Point pot[300];
18 Pleg peg[300];
19 Pleg Line;
20 
21 bool dbcmp(double x,double y){
22     if(fabs(x-y)<eps) return false;
23     return true;
24 }
25 
26 double multi(Point a,Point b, Point c,Point d){
27     return (a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x);
28 }
29 
30 bool slove(int k){
31     if(multi(peg[k].start,Line.start,Line.end,Line.start)*multi(Line.start,peg[k].end,Line.end,Line.start)>=0)
32     return true;
33     return false;
34 }
35 
36 int main(){
37     int T,n;
38     scanf("%d",&T);
39     while(T--){
40         how_point=how_pleg=0;
41         scanf("%d",&n);
42         for(int i=1;i<=n;i++){
43             scanf("%lf%lf",&pot[how_point].x,&pot[how_point].y);
44             peg[how_pleg].start=pot[how_point];
45             how_point++;
46             scanf("%lf%lf",&pot[how_point].x,&pot[how_point].y);
47             peg[how_pleg].end=pot[how_point];
48             how_point++;
49             how_pleg++;
50         }
51         bool flag=false;
52         for(int i=0;i<how_point;i++){
53             for(int j=i+1;j<how_point;j++){
54                 if(!dbcmp(pot[i].x,pot[j].x)&&!dbcmp(pot[i].y,pot[j].y))
55                 continue;
56                 Line.start=pot[i]; Line.end=pot[j];
57                 int k;
58                 for(k=0;k<how_pleg;k++){
59                     if(slove(k)){
60                         continue;
61                     }
62                     break;
63                 }
64                 if(k==how_pleg){
65                     flag=true;
66                     break;
67                 }
68             }
69             if(flag) break;
70         }
71         if(flag) printf("Yes!\n");
72         else printf("No!\n");
73     }
74     return 0;
75 }
View Code

POJ 3304,布布扣,bubuko.com

POJ 3304

原文:http://www.cnblogs.com/jie-dcai/p/3865954.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!