吴昊品游戏为主算法 Round 12(特别篇) —— 吴昊教你打筷子游戏(计算几何)

betway必威体育app官网 1

  

 筷子在古给(箸者,助也,意思是帮助吃饭的家伙。另:在闽南语地区、广东省和平县还有温州地域的土著人仍如筷子也,在闽南语地区念tî、广东省和平县拼音为chī,温州城区念dzei),又给。清朝赵翼曾引用明朝陆容的《菽园杂记》说:“起于吴中。凡舟行讳住讳翻,故呼箸为快子”(住和箸同音)。人类采取筷子的史足以追溯至三千年以前,《礼记·曲礼上》就有“饭黍母以箸”和“羹之出菜者用梜”的记载。由考古学提供的证据而言,筷子的面世晚于匙羹,同样由,由于众人怀念做某种工具为利于得烫热的烟火,所以筷子的阐明和原始农业和陶器的应用和前进有所直接涉及。

 筷子是孰发明,何时落地,历代虽起那么些传说,但实则难以考究。中国口历来都视筷子为自垂下来的寻常用品,对那个的由和进步只有为数不多之记载,或是有关的书就失传。

 

  我们打的玩耍大简单,地面上发生好多筷子,它们相互交叠在协同,我们需要找到的凡所有的太顶端之筷子,并拿其据号码从小至很顺次输出。

 输入有N行,每一行来4单数据,可以象征为(x1,y1,x2,y2),这里代表同样完完全全筷子的起始点。后面一行的筷子总是叠放在眼前一个筷子的上方。输出主要是遵照号码的尺寸顺序输出在极度上面的筷子的号。

  Solve:

 

 1  #include<iostream>
 2  #include<cstdio>
 3  #include<cstring>
 4  using namespace std;
 5  
 6  //将筷子的总和定义及10万横底数据级,再定义一个老有些好有些的累累,因为是double类型的,所以只要考虑到浮点误差
 7  const int maxn=100000+5;
 8  const double eps=1e-10;
 9  
10  //定义一个(x,y)的结构体
11  struct point
12  {
13    double x,y;       
14  };
15  
16  //每一个筷子都发生始端和后面,我们用p[maxn]和b[maxn]来作填这点儿端的值
17  point p[maxn],b[maxn];
18  //这里用0表示并未与任何一个筷子相交,只要出一个以上的筷子与那交,就象征也1,所以是bool逻辑的
19  bool ans[maxn];
20  
21  //double型的精打细算最小值函数
22  double min(double a,double b)
23  {
24    return a<b ? a:b;       
25  }
26  
27  //double型的计算最深价值函数
28  double max(double a,double b)
29  {
30    return a>b ? a:b;       
31  }
32  
33  //考虑是不是相交
34  bool inter(point a,point b,point c,point d)
35  {
36    //我们着想到要是某筷子的个别端的横/纵坐标都低于(或者高于)另外一个筷子的横/纵坐标,则可以祛除是inter的景
37    if( min(a.x, b.x)>max(c.x,d.x)||
38        min(a.y, b.y)>max(c.y,d.y)||
39        min(c.x, d.x)>max(a.x,b.x)||
40        min(c.y, d.y)>max(a.y, b.y) )
41     return 0;
42 
43     double h,i,j,k;
44 
45     h=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
46     i=(b.x-a.x)*(d.y-a.y)-(b.y-a.y)*(d.x-a.x);
47     j=(d.x-c.x)*(a.y-c.y)-(d.y-c.y)*(a.x-c.x);
48     k=(d.x-c.x)*(b.y-c.y)-(d.y-c.y)*(b.x-c.x);
49     
50     //用这四个变量判断是否相交,因为浮点数存在必然的误差,所以用eps来补一下
51     return h*i<=eps&&j*k<=eps;
52  }
53  
54  int main()
55  {
56    int n,i,j;
57    int res[maxn];
58    //如果遇到输入为0的场面,就退出
59    while(cin>>n,n)
60    {
61      //将
62      memset(ans,0,sizeof(ans));
63      for(i=0;i<n;i++)
64      {
65        //输入每个筷子的始端p和后b的坐标值
66        cin>>p[i].x>>p[i].y>>b[i].x>>b[i].y;               
67      }               
68      for(i=0;i<n;i++)
69      {
70        for(j=i+1;j<n;j++)
71        {
72          //判断筷子i与筷子j是休是碰头交,如果会交的话,就给记录
73          if(inter(p[i],b[i],p[j],b[j]))
74          {
75            ans[i]=1;
76            break;                              
77          }                  
78        }                
79      }
80      int ct=0;
81      cout<<“Top sticks:”;
82      for(i=0;i<n;i++)
83      {
84        //如果第i只筷子没有叫她之后的别样一个筷子相交的说话(之前的不要判断,因为即使是结交的讲话也终将会于她下面的)
85        if(!ans[i])
86          //这里要专注是i+1,因为数组是由0开始计数的
87          res[ct++]=i+1;
88      }
89      for(i=0;i<ct-1;i++)
90        cout<<res[i]<<“,”;
91      //最后一个独自输出
92      cout<<res[ct-1]<<“.”<<endl;  
93    }
94    return 0;    
95  }

 

                 

 

Post Author: admin

发表评论

电子邮件地址不会被公开。 必填项已用*标注