【poj2451】Uyuw’s Concert

2014年10月4日2,35213

Description

Prince Remmarguts solved the CHESS puzzle successfully. As an award, Uyuw planned to hold a concert in a huge piazza named after its great designer Ihsnayish.

The piazza in UDF – United Delta of Freedom’s downtown was a square of [0, 10000] * [0, 10000]. Some basket chairs had been standing there for years, but in a terrible mess. Look at the following graph.


In this case we have three chairs, and the audiences face the direction as what arrows have pointed out. The chairs were old-aged and too heavy to be moved. Princess Remmarguts told the piazza’s current owner Mr. UW, to build a large stage inside it. The stage must be as large as possible, but he should also make sure the audience in every position of every chair would be able to see the stage without turning aside (that means the stage is in the forward direction of their own).

To make it simple, the stage could be set highly enough to make sure even thousands of chairs were in front of you, as long as you were facing the stage, you would be able to see the singer / pianist – Uyuw.

Being a mad idolater, can you tell them the maximal size of the stage?

Input

In the first line, there’s a single non-negative integer N (N <= 20000), denoting the number of basket chairs. Each of the following lines contains four floating numbers x1, y1, x2, y2, which means there’s a basket chair on the line segment of (x1, y1) – (x2, y2), and facing to its LEFT (That a point (x, y) is at the LEFT side of this segment means that (x – x1) * (y – y2) – (x – x2) * (y – y1) >= 0).

Output

Output a single floating number, rounded to 1 digit after the decimal point. This is the maximal area of the stage.

Sample Input

Sample Output

Hint

Sample input is the same as the graph above, while the correct solution for it is as below:

I suggest that you use Extended in pascal and long double in C / C++ to avoid precision error. But the standard program only uses double.
求半平面交面积
上模板。。。

 

  • zzr2015年1月19日 下午7:33 回复

    jud和inter是求什么的

    #1  
    • zzr2015年1月19日 下午7:49 回复

      好吧,我是傻B,不用管我

      #11
  • guihuangxuezhang2015年4月28日 下午2:40 回复

    56,57行互换就会错,为啥要先弹栈顶呢??

    #2  
    • hzwer2015年4月28日 下午3:03 回复
      admin

      半平面交这是个坑点

      #21
      • guihuangxuezhang2015年4月28日 下午3:11 回复

        那为什么要先弹栈顶啊。。

        #22
        • hzwer2015年4月28日 下午7:38 回复
          admin

          不然边界会有问题。。。

          #23
          • guihuangxuezhang2015年4月28日 下午7:49

            噢。。thx黄学长

            #24
          • YJP2016年7月21日 下午7:52

            请问黄学长,边界问题是什么?

            #24
          • dkalkdlaskl2016年7月22日 上午11:22

            YJP

            #24
  • hzy98192016年1月7日 下午6:40 回复

    膜黄学长,为什么黄学长从不考虑精度却总是能过?
    l[i].angle!=l[i-1].angle等没三态函数不是很容易判错吗?

    #3  
    • hzwer2016年1月7日 下午11:08 回复
      admin

      不知道为什么。。。根据我的经验,精度过不了的题,特别是模板题,把eps设成0就能莫名其妙AC QwQ

      #31
    • hzwer2016年1月7日 下午11:22 回复
      admin

      我基本是有处理精度的吧,这里也不太清楚是怎么回事了

      #31
  • lhb2016年3月25日 下午3:39 回复

    黄学长的代码在poj上wa了

    #4