又开了一个坑= =

首先是tsinsen的A1420 裸的动态凸包

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define eps 1e-8
struct Point
 {
    double a1,a2;
 } t;
bool operator< (const Point &x,const Point &y)
 {  double d=atan2(x.a2-t.a2,x.a1-t.a1),f=atan2(y.a2-t.a2,y.a1-t.a1),
      o=(x.a1-t.a1)*(x.a1*t.a1)+(x.a2-t.a2)*(x.a2*t.a2),
      p=(y.a1-t.a1)*(y.a1*t.a1)+(y.a2-t.a2)*(y.a2*t.a2);
    return d+eps<f||fabs(d-f)<eps&&o<p;}
multiset <Point> li;
set <Point> :: iterator it,ti;
int n,m;
inline int Read()
 {
    int x=0;char y;bool z=0;
    do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
    do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
    return z?-x:x;
 }
void Set_up()
 {
    Point a[4];double q=0,w=0,e,k;int i,j,l;
    for (int i=1;i<=3;i++)
      Read(),k=Read(),e=Read(),a[i].a1=k,a[i].a2=e,q+=k,w+=e;
    t.a1=q/3;t.a2=w/3;
    for (int i=1;i<=3;i++) li.insert(a[i]);
    return;
 }
inline double Cha(Point x,Point y,Point z)
 {
    return ((y.a1-x.a1)*(z.a2-y.a2)-(y.a2-x.a2)*(z.a1-y.a1));
 }
void Insert(Point x)
 {
    int i,j,k,l;Point q,w,e;
    it=li.lower_bound(x);
    if (it==li.end()||it==li.begin())
      it=li.end(),q=*(--it),w=*(li.begin());else
      w=*(it--),q=*it;ti=it;
    if (Cha(q,x,w)<=eps) return;
    while (li.size()>2)
     {
        if (it==li.begin()) it=li.end();
        e=*(--it);
        if (Cha(e,q,x)<=eps)
          li.erase(ti);else break;
        ti=it;q=e;
     }
    it=ti=li.lower_bound(w);
    while (li.size()>2)
     {
        it++;if (it==li.end()) it=li.begin();
        e=*(it);
        if (Cha(x,w,e)<=eps)
          li.erase(ti);else break;
        ti=it;w=e;
     }
    li.insert(x);
    return;
 }
bool Check(Point x)
 {
    int i,j,k,l;Point q,w,e;
    if (x.a1==t.a1&&x.a2==t.a2) return 1;
    it=li.lower_bound(x);
    if (it==li.end()) it=li.begin();
    ti=it==li.begin()?li.end():it;ti--;
    return Cha(*ti,x,*it)<=eps;
 }
int main()
 {
    int i,j,q,w,e;Point k,l;
    scanf("%d",&n);
    li.clear();
    Set_up();
    for (i=4;i<=n;i++)
     {
        m=i;
        q=Read();k.a1=Read();k.a2=Read();
        if (q==1)
          Insert(k);else
        if (Check(k))
           printf("YES\n");else
           printf("NO\n");
     }
    return 0;
 }

然后是BZOJ1069，凸包+单调性乱搞

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 4050
#define eps 1e-8
#define INF 0x7f7f7f7f
struct Point
 {
 	double a1,a2;
 } a[N],mi;
int n,m,li[N],ri;
double ans=0;
bool operator== (const Point &x,const Point &y)
 {return fabs(x.a1-y.a1)<eps&&fabs(x.a2-y.a2)<eps;}
bool operator!= (const Point &x,const Point &y)
 {return fabs(x.a1-y.a1)>eps||fabs(x.a2-y.a2)>eps;}
inline double Cha(Point x,Point y,Point z)
 {return ((y.a1-x.a1)*(z.a2-y.a2)-(y.a2-x.a2)*(z.a1-y.a1));}
inline double sqr(double x)
 {return x*x;}
inline double dis(Point x,Point y)
 {return sqrt(sqr(x.a1-y.a1)+sqr(x.a2-y.a2));}
inline double max(double x,double y)
 {return x<y?y:x;}
inline double Square(Point x,Point y,Point z)
 {
 	return fabs((y.a1-x.a1)*(z.a2-x.a2)-(y.a2-x.a2)*(z.a1-x.a1))/2;
 }
inline bool cmp(Point x,Point y)
 {
 	double i=atan2(x.a2-a[n].a2,x.a1-a[n].a1),
 	   j=atan2(y.a2-a[n].a2,y.a1-a[n].a1);
 	return i+eps<j||(fabs(i-j)<eps&&dis(x,a[n])+eps<dis(y,a[n]));
 }
void Init()
 {
 	int i,k;
 	memset(li,0,sizeof(li));
 	scanf("%d",&n);
 	mi.a1=mi.a2=INF;
 	for (i=1;i<=n;i++)
 	 {
 	 	scanf("%lf%lf",&a[i].a1,&a[i].a2);
 	 	if (a[i].a1<mi.a1||(a[i].a1==mi.a1&&a[i].a2<mi.a2))
 	 	  mi=a[k=i];
 	 }
 	swap(a[k],a[n]);
 	return;
 }
void Graham()
 {
 	li[1]=n;li[ri=2]=1;
 	while (a[li[2]]==a[li[1]]&&li[2]<n) li[2]++;
 	if (li[2]==n) {ri--;return;}
 	for (int i=li[2]+1;i<n;i++)
 	 if (a[i]!=a[li[ri]])
 	  {
 	     while (ri-1&&Cha(a[li[ri-1]],a[li[ri]],a[i])+eps<0) ri--;
 	     li[++ri]=i;
 	  }
 	while (ri-2&&Cha(a[li[ri-1]],a[li[ri]],a[1])+eps<0) ri--;
 	return;
 }
void Solve()
 {
 	int i,j,k,l;double q,w,e;
 	for (i=1;i<=ri;i++) li[i+ri]=li[i];
 	for (i=1;i<ri;i++)
 	 {
 	 	k=0;j=i+1;q=0;w;
 	 	for (l=1;l<=ri;l++)
 	 	 if ((w=Square(a[li[i]],a[li[l]],a[li[j]]))>q)
 	 	   k=l,q=w;
 	 	l=i+1;
 	 	for (;j<=ri;j++)
 	 	 {
 	 	 	while (Square(a[li[i]],a[li[j]],a[li[k+1]])>
 	 	 		Square(a[li[i]],a[li[j]],a[li[k]])) k++;
 	 	 	while (l<j&&Square(a[li[i]],a[li[j]],a[li[l+1]])>
 	 	 	    Square(a[li[i]],a[li[j]],a[li[l]])) l++;
 	 	 	q=Square(a[li[i]],a[li[j]],a[li[l]]);
 	 	 	if (k!=l) q+=Square(a[li[i]],a[li[j]],a[li[k]]);
 	 	 	ans=max(ans,q);
 	 	 }
 	 }
 	return;
 }
int main()
 {
 	Init();
 	sort(a+1,a+n,cmp);
 	Graham();
 	Solve();
 	printf("%.3lf\n",ans);
 	return 0;
 }

BZOJ1043 裸的求圆交点

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
#define eps 1e-8
const double pi=acos(-1.0);
struct Point
 {
 	double a1,a2;
 } a[N],b[N];
double r[N],ans=0;
int n,m,ri;
inline double min(double x,double y)
 {return x<y?x:y;}
inline double max(double x,double y)
 {return x>y?x:y;}
inline double sqr(double x)
 {return x*x;}
inline double dis(Point x,Point y)
 {return sqrt(sqr(x.a1-y.a1)+sqr(x.a2-y.a2));}
inline double cmp(Point x,Point y)
 {return x.a1+eps<y.a1||(fabs(x.a1-y.a1)<eps&&x.a2<y.a2);}
inline bool Intersect(int x,int y)
 {
 	int i,j,k,l;double q=dis(a[x],a[y]),w,e;
 	if (q+eps>=r[x]+r[y]||(r[y]>r[x]&&r[y]-r[x]+eps>=q)) return 0;
 	if (q<=r[x]-r[y]+eps) return 1;
 	w=atan2(a[x].a2-a[y].a2,a[x].a1-a[y].a1);
 	e=acos((sqr(r[y])+sqr(q)-sqr(r[x]))/(2*r[y]*q));
 	b[ri].a1=w-e;b[ri].a2=w+e;
 	if (b[ri].a1+eps<-pi)
 	  b[++ri].a1=b[ri-1].a1+2*pi,b[ri].a2=pi,b[ri-1].a1=-pi;else
 	if (b[ri].a2>pi+eps)
 	  b[++ri].a2=b[ri-1].a2-2*pi,b[ri].a1=-pi,b[ri-1].a2=pi;
 	ri++;
 	return 0;
 }
double Solve(int x)
 {
 	int i,j,k,l;double q=0,w,e;ri=1;
 	for (i=1;i<x;i++)
 	  if (Intersect(i,x)) return 0;
 	sort(b+1,b+ri,cmp);
 	for (i=2;i<ri;i++)
 	 if (b[i].a1+eps<=b[i-1].a2)
 	   b[i].a1=min(b[i].a1,b[i-1].a1),
 	   b[i].a2=max(b[i].a2,b[i-1].a2),
 	   b[i-1].a1=b[i-1].a2=0;
 	for (i=1;i<ri;i++)
 	  q+=(b[i].a2-b[i].a1)*r[x];
 	return 2*pi*r[x]-q;
 }
int main()
 {
 	int i,j,k,l,q,w,e;
 	memset(r,0,sizeof(r));
 	scanf("%d",&n);
 	for (i=n;i>=1;i--)
 	  scanf("%lf%lf%lf",&r[i],&a[i].a1,&a[i].a2);
 	for (i=1;i<=n;i++)
 	  ans+=Solve(i);
 	printf("%.3lf\n",ans);
 	return 0;
 }

BZOJ2300：看一眼吓傻，完全不知道有删点的动态凸包怎么做= =只记得好像有论文上面提到过，感觉巨神于是没管了= =后来发现没有加点操作，就是倒着搞的SB题了= =。然后因为某些细节一直没调出来，后来坑到了数据才过了= =。

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define N 200050
#define eps 1e-9
struct Point
 {
  double a1,a2;
 } a[N];
set <Point> li;
set <Point> :: iterator it,ti;
int n,m,qu[N][2];double ans=0,cnt[N];bool b[N];
inline int Read()
 {
  int x=0;char y;
  do y=getchar(); while (y<'0'||y>'9');
  do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
  return x;
 }
inline double sqr(double x)
 {return x*x;}
inline double dis(Point x,Point y)
 {return sqrt(sqr(x.a1-y.a1)+sqr(x.a2-y.a2));}
inline double Cha(Point x,Point y,Point z)
 {return (y.a1-x.a1)*(z.a2-y.a2)-(y.a2-x.a2)*(z.a1-y.a1);}
bool operator< (const Point &x,const Point &y)
 { double q=atan2(x.a2,x.a1),w=atan2(y.a2,y.a1);
  return q+eps<w||(fabs(q-w)<eps&&x.a1*x.a1+x.a2*x.a2<
   y.a1*y.a1+y.a2*y.a2);}
void Set_up()
 {
  int i,j;Point k,l;double q=Read(),w=Read(),e=Read();
  li.insert(k=(Point){q,0});li.insert(l=(Point){w,e});
  li.insert((Point){0,eps});
  ans=dis((Point){0,0},l)+dis(l,k);
  return;
 }
inline void Insert(Point x)
 {
  int i,j;Point k,l;double q,w,e;
  it=li.lower_bound(x);ti=it;ti--;k=*it;l=*ti;
  if (Cha(l,x,k)<=eps) return;
  ans=ans-dis(k,l);
  do
  {
  ti=it;++it;
  if (it==li.end()||Cha(x,*ti,*it)>eps) break;
  ans=ans-dis(*ti,*it);
  li.erase(ti);
  } while (1);
  ans+=dis(x,*ti);
  it=li.lower_bound(l);
  do
  {
  ti=it;--it;
  if (ti==li.begin()||Cha(*it,*ti,x)>eps) break;
  ans=ans-dis(*ti,*it);
  li.erase(ti);
  } while (1);
  ans+=dis(x,*ti);li.insert(x);
  return;
 }
void Solve()
 {
  for (int i=1;i<=m;i++)
  if (qu[i][0]==1) b[qu[i][1]]=1;
  for (int i=1;i<=n;i++)
  if (!b[qu[i][0]])
    Insert(a[i]);
  for (int i=m;i>=1;i--)
  if (qu[i][0]==2)
    cnt[i]=ans;else
   Insert(a[qu[i][1]]);
  for (int i=1;i<=m;i++)
  if (qu[i][0]==2)
    printf("%.2lf\n",cnt[i]);
  return;
 }
int main()
 {
  int i,j,k,l,q,w,e;
  memset(qu,0,sizeof(qu));memset(b,0,sizeof(b));
  memset(cnt,0,sizeof(cnt));
  Set_up();n=Read();
  for (i=1;i<=n;i++)
   a[i].a1=Read(),a[i].a2=Read();
  m=Read();
  for (i=1;i<=m;i++)
  {
  qu[i][0]=Read();
  if (qu[i][0]==1) qu[i][1]=Read();
  }
  Solve();
  return 0;
 }

maya颓了好久终于把这个鬼畜半平面交搞出来了，要注意的是跟前面一样，“孩子cmp函数写挫了你就废了”，被一堆细节wa了n次= =

BZOJ2618：裸半平面交，坑比的是在BZOJ上过得了在codevs上怎么都过不了= =本来以为是有什么猥琐的细节，但是换了4个其他程序用出错的数据拍了n久硬是没发现问题。话说这个感觉还是写的好丑【捂脸贼】

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
#define eps 1e-8
const double pi=acos(-1.0);
struct Point
 {
 	double x,y;
 } b[N];
struct Line
 {
 	Point x,y;double v;
 } a[N];
int n=0,m,t,ri,li[N],le=1;double ans=0;
Point operator+ (const Point &x,const Point &y)
 {return (Point){x.x+y.x,x.y+y.y};}
Point operator- (const Point &x,const Point &y)
 {return (Point){x.x-y.x,x.y-y.y};}
double operator* (const Point &x,const Point &y)
 {return x.x*y.y-x.y*y.x;}
inline bool cmp(Line x,Line y)
 {
 	if (x.v!=y.v) return x.v<y.v;
 	return (x.y-x.x)*(y.y-x.x)>0;
 }
inline int Read()
 {
 	int x=0;char y;bool z=0;
 	do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return z?-x:x;
 }
inline Point Intersect(Line x,Line y)
 {
 	double k=(y.x-x.x)*(y.y-x.x),l=(y.y-x.y)*(y.x-x.y);
 	double q=k/(k+l);Point p;p=x.y-x.x;
 	p.x=x.x.x+p.x*q;p.y=x.x.y+p.y*q;
 	return p;
 }
inline bool Cao(Line x,Line y,Line z)
 {
 	Point k=Intersect(x,y);
 	return (k-z.x)*(k-z.y)<=eps;
 }
void Solve()
 {
 	int i,j;Point k,l;double q,w,e;int tot=0;
 	sort(a+1,a+n+1,cmp);
 	a[n+1].v=-2*pi;
 	for (i=1;i<=n;i++)
 	 {
 	 	if (a[i].v!=a[i-1].v) tot++;
 	 	a[tot]=a[i];
 	 }
  	li[ri=1]=1;le=1;li[ri=2]=2;n=tot;
 	for (i=3;i<=n;i++)
 	     {
 	while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[i])) ri--;
 	while (ri-le&&Cao(a[li[le+1]],a[li[le]],a[i])) le++;
 	  	    li[++ri]=i;
 	     }
 	while (ri-le&&Cao(a[li[ri]],a[li[le]],a[li[le+1]])) le++;
 	while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[li[le]])) ri--;
 	for (i=le;i<ri;i++)
 	  b[i-le+1]=Intersect(a[li[i]],a[li[i+1]]);
 	b[ri-le+1]=Intersect(a[li[ri]],a[li[le]]);
 	if (ri-le+1<3) return;
 	for (i=1,ri=ri-le+1;i<ri;i++)
 	  ans+=b[i]*b[i+1];
 	ans+=b[ri]*b[1];
 	return;
 }
int main()
 {
 	t=Read();
 	for (int i=1;i<=t;i++)
 	 {
 	 	Point q,w,e;
 	 	m=Read();q.x=Read(),q.y=Read();w=q;
 	 	for (int j=2;j<=m;j++)
 	 	  e.x=Read(),e.y=Read(),a[++n]=(Line){w,e,
 	 	    atan2(e.y-w.y,e.x-w.x)},w=e;
 	 	a[++n]=(Line){w,q,atan2(q.y-w.y,q.x-w.x)};
 	 }
 	Solve();
 	printf("%.3lf\n",ans/2);
 	return 0;
 }

BZOJ1038瞭望塔：又是一个半平面交的裸题，又被细节坑了好久= =

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
#define M 1e12
#define eps 1e-8
const double pi=acos(-1.0);
struct Point
 {
 	double x,y;
 } b[N],c[N];
struct Line
 {
 	Point x,y;double v;
 } a[N];
int n=0,m=0,li[N];
double ans=2*M;
Point operator+ (const Point &x,const Point &y)
 {return (Point){x.x+y.x,x.y+y.y};}
Point operator- (const Point &x,const Point &y)
 {return (Point){x.x-y.x,x.y-y.y};}
double operator* (const Point &x,const Point &y)
 {return x.x*y.y-x.y*y.x;}
bool operator< (const Line &x,const Line &y)
 {return x.v!=y.v?x.v<y.v:(x.y-x.x)*(y.y-x.x)>0;}
inline double min(double x,double y)
 {return x<y?x:y;}
inline double sqr(double x)
 {return x*x;}
inline double dis(Point x,Point y)
 {return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));}
inline int Read()
 {
 	int x=0;char y;bool z=0;
 	do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return z?-x:x;
 }
inline Point Intersect(Line x,Line y)
 {
 	double q=(y.x-x.x)*(y.y-x.x),w=(y.y-x.y)*(y.x-x.y);
 	w=q/(w+q);Point e=x.y-x.x;e.x=x.x.x+e.x*w;
 	e.y=x.x.y+e.y*w;return e;
 }
inline bool Cao(Line x,Line y,Line z)
 {Point k=Intersect(x,y);return (k-z.x)*(k-z.y)<=eps;}
void Set_up()
 {
 	int i,j;Point k,l,q,w,e;
 	n=Read();
 	for (i=1;i<=n;i++) b[i].x=Read();
 	for (i=1;i<=n;i++) b[i].y=Read();
 	m=n-1;
    for (i=1;i<=m;i++)
      a[i].x=b[i],a[i].y=b[i+1],
       a[i].v=atan2(b[i+1].y-b[i].y,b[i+1].x-b[i].x);
    k.x=k.y=l.x=w.y=-M;q.x=q.y=l.y=w.x=M;
    a[++m].x=w;a[m].y=q;a[m].v=pi/2;
    a[++m].x=q;a[m].y=l;a[m].v=pi;
    a[++m].x=l;a[m].y=k;a[m].v=-pi/2;
    a[++m].x=k;a[m].y=w;a[m].v=0;
    return;
 }
void Half_Inter()
 {
 	int i,j,tot=0,le,ri;Point k,l;double q,w,e;
 	sort(a+1,a+m+1);
 	for (i=1;i<=m;i++)
     {
     	if (a[i].v!=a[i-1].v) tot++;
     	a[tot]=a[i];
     }
    le=1;ri=2;li[1]=1;li[2]=2;
    for (i=3;i<=tot;i++)
     {
     	while (ri-le&&Cao(a[li[le]],a[li[le+1]],a[i])) le++;
     	while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[i])) ri--;
     	li[++ri]=i;
     }
    while (ri-le&&Cao(a[li[ri]],a[li[le]],a[li[le+1]])) le++;
    while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[li[le]])) ri--;
    for (i=le,ri=m=ri-le+1;i<le+ri-1;i++)
      c[i-le+1]=Intersect(a[li[i]],a[li[i+1]]);
    c[ri]=Intersect(a[li[le]],a[li[le+ri-1]]);
    return;
 }
inline void Check(Point x)
 {
 	Line q;int i;q.x=q.y=x;q.y.y=M+1;
 	if (x.x<b[1].x||x.x>b[n].x) return;
 	for (int i=1;i<n;i++)
 	 if (x.x>=b[i].x&&x.x<=b[i+1].x)
 	   ans=min(ans,dis(Intersect(q,(Line){b[i],b[i+1],0}),x));
 	return;
 }
inline void cHeck(Point x)
 {
 	Line q;int i;q.x=q.y=x;q.y.y=-M-1;
 	for (int i=1;i<m;i++)
 	 if ((x.x>=c[i].x)^(x.x>c[i+1].x))
 	   ans=min(ans,dis(Intersect(q,(Line){c[i],c[i+1],0}),x));
 	return;
 }
int main()
 {
 	memset(li,0,sizeof(li));
 	Set_up();
 	Half_Inter();
 	for (int i=1;i<=m;i++) Check(c[i]);
 	for (int i=1;i<=n;i++) cHeck(b[i]);
    printf("%.3lf\n",ans);
    return 0;
 }

BZOJ3190赛车：也是裸半平面交，真是一路wa。TATQAQ2333改完细节之后代码好丑= =

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 10050
#define eps 1e-8
const double pi=acos(-1.0);
struct Point
 {
 	double x,y;
 };
struct Line
 {
 	Point x,y;double v;int sg;
 } a[N];
int n,m,s=0,li[N],le,ri;bool c[N];
Point operator+ (const Point &x,const Point &y)
 {return (Point){x.x+y.x,x.y+y.y};}
Point operator- (const Point &x,const Point &y)
 {return (Point){x.x-y.x,x.y-y.y};}
double operator* (const Point &x,const Point &y)
 {return x.x*y.y-x.y*y.x;}
bool operator< (const Line &x,const Line &y)
 {return (x.v<y.v)||(x.v==y.v&&(x.y-x.x)*(y.y-x.x)>eps);}
bool operator!= (const Point &x,const Point &y)
 {return x.x!=y.x||x.y!=y.y;}
bool operator!= (const Line &x,const Line &y)
 {return x.v!=y.v||x.x!=y.x;}
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
inline Point Intersect(Line x,Line y)
 {
 	Point e;double q=(y.x-x.x)*(y.y-x.x),w=(y.y-x.y)*(y.x-x.y);
 	w=q/(q+w);e=x.y-x.x;e.x=x.x.x+e.x*w;e.y=x.x.y+e.y*w;
  	return e;
 }
inline bool Cao(Line x,Line y,Line z)
 {Point k=Intersect(x,y);return (k-z.x)*(k-z.y)<-eps;}
void Half_Inter()
 {
 	int i,j,tot=0;Point k,l,q,w,e;
 	sort(a+1,a+n+1);i=1;k.x=0;
 	while (i<n) {if (a[i]!=a[i+1]) k=Intersect(a[i],a[i+1]);if (k.x>-eps) break;i++;}
 	li[1]=i;li[2]=i+1;le=1;ri=2;
    if (i==n) ri--;
 	for (i+=2;i<=n;i++)
 	 {
 	 	while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[i])) ri--;
 	 	li[++ri]=i;
 	 }
 	while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[li[le]])) ri--;
 	while (ri-le)
 	 {
 	 	i=le;while (i<ri&&!(a[li[i]]!=a[li[i+1]])) i++;
 	    if (i==ri) break;
 	    k=Intersect(a[li[i]],a[li[i+1]]);
        if (k.x>-eps) break;le=i+1;
     }
 	return;
 }
int main()
 {
 	int j;
 	memset(li,0,sizeof(li));memset(c,0,sizeof(c));
 	scanf("%d",&n);
 	for (int i=1;i<=n;i++) a[i].x.y=a[i].y.y=Read();
 	for (int i=1;i<=n;i++) a[i].y.y+=(a[i].v=Read()),
 	  a[i].y.x=1,a[i].sg=i;
 	Half_Inter();
    printf("%d\n",ri-le+1);
    for (int i=le;i<=ri;i++)
      c[a[li[i]].sg]=1;
    for (j=1;j<=n;j++)
     {
        if (c[j])
         {
         	if (ri-le) printf("%d ",j);else
         	  printf("%d\n",j);
        le++;
         }
     }
 	return 0;
 }

BZOJ1027合金：看上去是三维球面上面的问题，实际上因为是球面，所以投影到坐标系平面上面问题还是等价的。然后就暴力建边跑floyd（之前一直以为n^3会比较有危险，而且还是这种时限四秒题，总觉得还有其它方法，真是naive！）。还有要注意题目里面的细节比如答案为1或2的时候要做讨论，真心被坑wa了n次

话说为毛每次我的笔记作了20页就会丢，真是丧心= =

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 550
#define eps 1e-8
#define INF 0x3f3f3f3f
struct Point
 {
 	double x,y;
 } a[N],b[N];
Point operator- (const Point &x,const Point &y)
 {return (Point){x.x-y.x,x.y-y.y};}
double operator* (const Point &x,const Point &y)
 {return x.x*y.y-x.y*y.x;}
bool operator== (const Point &x,const Point &y)
 {return fabs(x.x-y.x)<eps&&fabs(x.y-y.y)<eps;}
int n,m,ss,h[N][N],tot=0,ans=INF;
inline int Calc(Point x,Point y)
 {
 	for (int i=1;i<=m;i++)
 	 {
 	 	double q=(y-x)*(b[i]-x);
 	 	if (fabs(q)>eps&&q<0) return INF;
 	 	if (fabs(q)<eps&&((b[i].x-y.x)*(y.x-x.x)>eps||
 	 	  (b[i].y-y.y)*(y.y-x.y)>eps)) return INF;
 	 	if (fabs(q)<eps&&((b[i].x-x.x)*(x.x-y.x)>eps||
 	 	  (b[i].y-x.y)*(x.y-y.y)>eps)) return INF;
 	 }
 	return 1;
 }
bool Check()
 {
 	if (m==1)
 	 for (int i=1;i<=n;i++)
 	  if (a[i]==b[1])
 	   {
 	   	  printf("1\n");return 1;
 	   }
 	for (int i=3;i<=m;i++)
 	 if (fabs((b[i]-b[1])*(b[2]-b[1]))>eps) return 0;
 	if (m==1) b[2]=b[1];
 	for (int i=1;i<n;i++)
 	 for (int j=i+1;j<=n;j++)
 	  if (fabs((a[j]-a[i])*(b[2]-b[1]))<eps)
 	   for (int k=1;k<=m;k++)
 	    {
 	       double l=b[k].x-a[i].x,q=b[k].x-a[j].x,
 	         w=b[k].y-a[i].y,e=b[k].y-a[j].y;
 	       if (fabs((a[i]-b[k])*(a[j]-b[k]))>eps) continue;
 	       if ((fabs(l)>eps&&fabs(q)>eps&&l*q>0)||
 	       	 (fabs(w)>eps&&fabs(e)>eps&&w*e>0)) continue;
 	       printf("2\n");return 1;
 	    }
 	return 0;
 }
int main()
 {
 	memset(h,0,sizeof(h));
 	scanf("%d%d",&n,&m);a[0].x=b[0].x=-1;
 	for (int i=1;i<=n;i++)
 	 {
 	    scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[0].y);
 	    if (a[i].x!=a[i-1].x||a[i].y!=a[i-1].y) tot++;
 	    a[tot]=a[i];
 	 }
 	n=tot;tot=0;
 	for (int i=1;i<=m;i++)
 	 {
 	    scanf("%lf%lf%lf",&b[i].x,&b[i].y,&b[0].y);
 	    if (b[i].x!=b[i-1].x||b[i].y!=b[i-1].y) tot++;
 	    b[tot]=b[i];
 	 }
 	m=tot;if (Check()) return 0;
 	for (int i=1;i<=n;i++)
 	 for (int j=1;j<=n;j++)
 	   h[i][j]=i!=j?Calc(a[i],a[j]):INF;
 	for (int k=1;k<=n;k++)
 	 for (int i=1;i<=n;i++)
 	  for (int j=1;j<=n;j++)
 	    h[i][j]=min(h[i][j],h[i][k]+h[k][j]);
 	for (int i=1;i<=n;i++)
 	  ans=min(ans,h[i][i]);
 	printf("%d\n",ans==INF?-1:ans);
 	return 0;
 }