计算几何-poj2451-HPI-白红宇

计算几何-poj2451-HPI

阅读量：6004 次

发布时间：2019-06-20

本文共 958 字，大约阅读时间需要 3 分钟。

This article is made by Jason-Cow.

Welcome to reprint.
But please post the article's address.

题意，求半平面交，并且保证有解

给张图边界（|x,y|<=1000,题目为1e4）

别问我为什么TLE

我当成多组处理没有判断文末符号，加上就！A！啦！

直接上模板

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include 
              10 #include 
              
                11 using namespace std; 12 #define sqr(x) ((x)*(x)) 13 #define RG register 14 #define op operator 15 #define IL inline 16 typedef double db; 17 typedef bool bl; 18 const db pi=acos(-1.0),eps=1e-10; 19 struct D{ 20 db x,y; 21 D(db x=0.0,db y=0.0):x(x),y(y){} 22 }; 23 typedef D V; 24 bl operator<(D A,D B){ return A.x
               
                
                 0; 63 } 64 65 int HPI(L*l,int n,D*ans){ 66 int head,tail,m=0; 67 D*P=new D[n];L*q=new L[n]; 68 sort(l+1,l+n+1),q[head=tail=0]=l[1]; 69 for(int i=2;i<=n;i++){ 70 while(head