bzoj1007题解

【题意分析】
　　给你n个上半平面，求包含这些上半平面的交的上半平面。
【解题思路】
　　按斜率排序，用单调栈维护一个下凸壳即可。复杂度O(nlog₂n)。
【参考代码】
 #include <cctype>

 #include <cmath>

 #include <cstdio>

 #define REP(I,start,end) for(int I=(start);I<=(end);I++)

 #define PER(I,start,end) for(int I=(start);I>=(end);I--)

 inline int space()

 {

     return putchar(' ');

 }

 inline int enter()

 {

     return putchar('\n');

 }

 inline bool eoln(char ptr)

 {

     return ptr=='\n';

 }

 inline bool eof(char ptr)

 {

     return ptr=='\0';

 }

 inline int getint()

 {

     char ch=getchar();

     for(;!isdigit(ch)&&ch!='+'&&ch!='-';ch=getchar());

     bool impositive=ch=='-';

     if(impositive)

         ch=getchar();

     int result=;

     for(;isdigit(ch);ch=getchar())

         result=(result<<)+(result<<)+ch-'';

     return impositive?-result:result;

 }

 template<typename integer> inline int write(integer n)

 {

     integer now=n;

     bool impositive=now<;

     if(impositive)

     {

         putchar('-');

         now=-now;

     }

     char sav[];

     sav[]=now%+'';

     int result=;

     for(;now/=;sav[result++]=now%+'');

     PER(i,result-,)

         putchar(sav[i]);

     return result+impositive;

 }

 template<typename real> inline bool fequals(real one,real another,real eps=1e-)

 {

     return fabs(one-another)<eps;

 }

 template<typename real> inline bool funequals(real one,real another,real eps=1e-)

 {

     return fabs(one-another)>=eps;

 }

 template<typename T=double> struct Point

 {

     T x,y;

     Point()

     {

         x=y=;

     }

     Point(T _x,T _y)

     {

         x=_x;

         y=_y;

     }

     bool operator==(const Point<T> &another)const

     {

         return fequals(x,another.x)&&fequals(y,another.y);

     }

     bool operator!=(const Point<T> &another)const

     {

         return funequals(x,another.x)||funequals(y,another.y);

     }

     Point<T> operator+(const Point<T> &another)const

     {

         Point<T> result(x+another.x,y+another.y);

         return result;

     }

     Point<T> operator-(const Point<T> &another)const

     {

         Point<T> result(x-another.x,y-another.y);

         return result;

     }

     Point<T> operator*(const T &number)const

     {

         Point<T> result(x*number,y*number);

         return result;

     }

     Point<double> operator/(const T &number)const

     {

         Point<double> result(double(x)/number,double(y)/number);

         return result;

     }

     double theta()

     {

         return x>?(y<)**M_PI+atan(y/x):M_PI+atan(y/x);

     }

     double theta_x()

     {

         return !x?M_PI/:atan(y/x);

     }

     double theta_y()

     {

         return !y?M_PI/:atan(x/y);

     }

 };

 template<typename T> inline T dot_product(Point<T> A,Point<T> B)

 {

     return A.x*B.x+A.y*B.y;

 }

 template<typename T> inline T cross_product(Point<T> A,Point<T> B)

 {

     return A.x*B.y+A.y*B.x;

 }

 template<typename T> inline T SqrDis(Point<T> a,Point<T> b)

 {

     return sqr(a.x-b.x)+sqr(a.y-b.y);

 }

 template<typename T> inline double Euclid_distance(Point<T> a,Point<T> b)

 {

     return sqrt(SqrDis(a,b));

 }

 template<typename T> inline T Manhattan_distance(Point<T> a,Point<T> b)

 {

     return fabs(a.x-b.x)+fabs(a.y-b.y);

 }

 template<typename T=double> struct kbLine

 {

     //line:y=kx+b

     T k,b;

     kbLine()

     {

         k=b=;

     }

     kbLine(T _k,T _b)

     {

         k=_k;

         b=_b;

     }

     bool operator==(const kbLine<T> &another)const

     {

         return fequals(k,another.k)&&fequals(b,another.b);

     }

     bool operator!=(const kbLine<T> &another)const

     {

         return funequals(k,another.k)||funequals(b,another.b);

     }

     bool operator<(const kbLine<T> &another)const

     {

         return k<another.k;

     }

     bool operator>(const kbLine<T> &another)const

     {

         return k>another.k;

     }

     template<typename point_type> inline bool build_line(Point<point_type> A,Point<point_type> B)

     {

         if(fequals(A.x,B.x))

             return false;

         k=T(A.y-B.y)/(A.x-B.x);

         b=A.y-k*A.x;

         return true;

     }

     double theta_x()

     {

         return atan(k);

     }

     double theta_y()

     {

         return theta_x()-M_PI/;

     }

 };

 template<typename T> bool parallel(kbLine<T> A,kbLine<T> B)

 {

     return A!=B&&(fequals(A.k,B.k)||A.k!=A.k&&B.k!=B.k);

 }

 template<typename T> Point<double> *cross(kbLine<T> A,kbLine<T> B)

 {

     if(A==B||parallel(A,B))

         return NULL;

     double _x=double(B.b-A.b)/(A.k-B.k);

     Point<double> *result=new Point<double>(_x,A.k*_x+A.b);

     return result;

 }

 //======================================Header Template=====================================

 #include <algorithm>

 using namespace std;

 int stack[];

 struct _line

 {

     kbLine<> _l;

     int order;

     bool operator<(const _line &T)const

     {

         return _l<T._l||parallel(_l,T._l)&&_l.b>T._l.b;

     }

 }lines[];

 inline bool Order(int A,int B)

 {

     return lines[A].order<lines[B].order;

 }

 int main()

 {

     int n=getint();

     REP(i,,n)

     {

         lines[i].order=i;

         scanf("%lf%lf",&lines[i]._l.k,&lines[i]._l.b);

     }

     sort(lines+,lines+n+);

     int top=stack[]=,i=;

     while(i<=n)

     {

         for(;i<=n&&(lines[i]._l==lines[stack[top]]._l||parallel(lines[i]._l,lines[stack[top]]._l));i++);

         for(;i<=n&&top>;top--)

         {

             Point<double> *last=cross(lines[stack[top-]]._l,lines[stack[top]]._l),*now=cross(lines[i]._l,lines[stack[top]]._l);

             if(last->x<now->x)

                 break;

         }

         stack[++top]=i++;

     }

     sort(stack+,stack+top+,Order);

     REP(i,,top)

     {

         write(lines[stack[i]].order);

         space();

     }

     enter();

     return ;

 }
巴特西

bzoj1007题解

最新文章

热门文章
