ccgeo
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
组队赛中WA过的提交，原因，所犯的2B错误：
1. burnside，最后除的N必须是置换群的准确size
2. 圆交：>90度角用中点求内积相加得到
3. 圆交：区间必须记录后一起搞，可以离散化、扫描线
4. 圆交：必须去除0长度的区间，会影响最后结果计算。
5. 偷懒把mark清零写到for循环上，结果清零的个数是N不是T，太新手了！
6. 没考虑DEP[I]（火车发车时间）,一个读入变量在程序中没被用到也没发现，丢！！
7. 当你发现模型是NPC问题，说明一定有附加条件！
8. 因为枚举的k要经过k%N==0的检查，于是我干脆枚举k时for k=N ; ;k+=N，
但是tot/k可能%N==0没被枚举到！
9. 求一个边权全部为1的有向图最短路，用dijkastra卡到死，这不就是个BFS吗
10. 爽了把299，当中间过程跑出负权环但不能最终到达终点，则该无视之！
11. 用map作离散化，超时到死，按题目实际情况考虑有没有更高效的方法
12. 线段树也可以不下传，比如用它做矩形并的时候。
13. 数量少时多用容斥的技巧思考问题
14. 开数组时思考大小是否够用，开变量时思考是否够存
15. 虽然是SPJ题 输出顺序有时也有规定
16. 向量旋转，WA到死，eps大到1e-5后AC
17. 用扫描线做计算几何时，未清晰考虑共线事件，
将弧度大小判断改成队列位置判断是否穿越-pi线，AC
18. 做几何题物理题的时候，看清楚各个输入数据的单位是什么！
19. 位压一个10位的数字，用while(k)WA到死，在有前置0的时候
20. DFA判相似的时候（以及类似图论题），应该无视不能到达danger点的那些结点！
个人选拔赛中WA过的提交，2B错误：
1. 有-操作，记得+mod)%mod
2. 2亿的数组也敢开，滚起啊
3. 次奥，哈夫曼编码也能忘？？
4. 手贱用某函数是否返回-1判数据合法性，结果没设置函数默认返回值TLE到死
5. 手贱加输入特判，又没人肉对，改后AC
6. 写个BFS，mark都忘记清
7. 高精度自动机DP 位数没开足
8.
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct point{double x,y;};
struct line{point a,b;};
//计算dot product (P1-P0).(P2-P0)
double dmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
//计算cross product (P1-P0)x(P2-P0)
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dist(point p1,point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
//判三点共线
int dots_inline(point p1,point p2,point p3){
return zero(xmult(p1,p2,p3));
}
//判点是否在线段上,包括端点
int dot_online_in(point p,line l){
return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps;
}
//判两点在线段同侧,点在线段上返回0
int same_side(point p1,point p2,line l){
return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;
}
//判两直线平行
int parallel(line u,line v){
return zero((u.a.x-u.b.x)*(v.a.y-v.b.y)-(v.a.x-v.b.x)*(u.a.y-u.b.y));
}
//判两线段相交,包括端点和部分重合
int intersect_in(line u,line v){
if (!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b))
return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);
return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u);
}
//线段交点请另外判线段相交(同时还是要判断是否平行!)
point intersection(line u,line v){
point ret=u.a;
double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))
/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
ret.x+=(u.b.x-u.a.x)*t;
ret.y+=(u.b.y-u.a.y)*t;
return ret;
}
//判断直线是否和线段相交
int str_line_seg_in(point p1,point p2,line v){
if (dots_inline(p1,p2,v.a)||dots_inline(p1,p2,v.b)) return true;
line u;
u.a = p1,u.b = p2;
return !same_side(v.a,v.b,u);
}
//两条不相交线段间的最短距离
double seg_dist(point a0,point a1,point b0,point b1){
double ans = dist(a0,b0),tmp;
checkmin(ans,dist(a0,b1));
checkmin(ans,dist(a1,b0));
checkmin(ans,dist(a1,b1));
if (dist(b0,b1)>0){
if (dmult(b0,b1,b0,a0)>=0&&dmult(b1,b0,b1,a0)>=0){
tmp = xmult(b0,b1,b0,a0)/dist(b0,b1);
checkmin(ans,fabs(tmp));
}
if (dmult(b0,b1,b0,a1)>=0&&dmult(b1,b0,b1,a1)>=0){
tmp = xmult(b0,b1,b0,a1)/dist(b0,b1);
checkmin(ans,fabs(tmp));
}
}
if (dist(a0,a1)>0){
if (dmult(a0,a1,a0,b0)>=0&&dmult(a1,a0,a1,b0)>=0){
tmp = xmult(a0,a1,a0,b0)/dist(a0,a1);
checkmin(ans,fabs(tmp));
}
if (dmult(a0,a1,a0,b1)>=0&&dmult(a1,a0,a1,b1)>=0){
tmp = xmult(a0,a1,a0,b1)/dist(a0,a1);
checkmin(ans,fabs(tmp));
}
}
return ans;
}
//凸包可解决问题系列，旋转卡壳
//计算凸包，共线点是否保留修改>=0
bool cmp(point a,point b){
return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
void calc(int N){
int i,cnt ;
double xa;
sort(P,P+N,cmp);
cnt = 0;
Q[cnt++] = 0;
for (i=1;i<N;)
if (cnt==1||xmult(P[Q[cnt-1]],P[i],P[Q[cnt-2]])>=0)
Q[cnt++] = i++;
else cnt--;
int top = cnt;
for (i=N-2;i>=0;)
if (cnt==top||xmult(P[Q[cnt-1]],P[i],P[Q[cnt-2]])>=0)
Q[cnt++] = i--;
else cnt--;
return ;
//旋转卡壳求最远点对
Q[cnt] = Q[1];
ans = 0;
for (i=0,j=top-1;i<top&&j<cnt;){
ans = max(ans,sqr(P[Q[i]].x-P[Q[j]].x)+sqr(P[Q[i]].y-P[Q[j]].y));
if (xmult(P[Q[i]],P[Q[i+1]],P[Q[j]],P[Q[j+1]])<0) i++;
else j++;
}
//旋转卡壳求两凸包间最短距离，需要seg_dist函数
sort(A,A+N,cmp);
int n1 = getQ(N,A,Q1);
sort(B,B+M,cmp2);
int n2 = getQ(M,B,Q2);
ans = dist(A[0],B[0]);
for (i=0,j=0;i<n1&&j<n2;){
checkmin(ans, seg_dist(A[Q1[i]],A[Q1[i+1]],B[Q2[j]],B[Q2[j+1]]));
if (xmult(A[Q1[i]],A[Q1[i+1]],B[Q2[j]],B[Q2[j+1]])<0) i++;
else j++;
}
//============================
//旋转卡壳求最小面积外接矩形
double lx = 1e100,rx = -1e100;
int j,L,R;
for (i=0;i<cnt;i++){
if (lx>P[Q[i]].x) lx = P[Q[i]].x,L = i;
if (rx<P[Q[i]].x) rx = P[Q[i]].x,R = i;
}
for (i=0,j=top-1;i<cnt-1;i++){
while(xmult(P[Q[i]],P[Q[i+1]],P[Q[j]],P[Q[j+1]])>0)
{
j++;
if (j==cnt-1) j = 0;
}
while(dmult(P[Q[i]],P[Q[i+1]],P[Q[L]],P[Q[L+1]])<0){
L++;
if (L==cnt-1) L = 0;
}
while(dmult(P[Q[i]],P[Q[i+1]],P[Q[R]],P[Q[R+1]])>0){
R++;
if (R==cnt-1) R = 0;
}
ans = min(ans, fabs(xmult(P[Q[i]],P[Q[i+1]],P[Q[i]],P[Q[j]])
*(dmult(P[Q[i]],P[Q[i+1]],P[Q[i]],P[Q[R]])
-dmult(P[Q[i]],P[Q[i+1]],P[Q[i]],P[Q[L]]))
/distsqr(P[Q[i]],P[Q[i+1]])));
}
return ;
/*
* 旋转卡壳求点集组成最大三角形面积
* 不断调整卡壳线，不能调整时手动将第一条线前移
* POJ数据过水，attention the code
*/
int tot = polygen();
i= 0 ,j = 1,k =2;
double ans = 0;
while(1){
int bi = i,bj = j,bk = k;
while(k<tot&&fabs(xmult(Q[i],Q[j],Q[k]))<fabs(xmult(Q[i],Q[j],Q[k+1])))
k++;
while(j<k&&fabs(xmult(Q[i],Q[j],Q[k]))<fabs(xmult(Q[i],Q[j+1],Q[k])))
j++;
while(i<j&&fabs(xmult(Q[i],Q[j],Q[k]))<fabs(xmult(Q[i+1],Q[j],Q[k])))
i++;
ans = max(ans,xmult(Q[i],Q[j],Q[k]));
if (bi==i&&bj==j&&bk==k)
k++;
if (k==tot) break;
}
printf("%.2lf\n",ans/2);
return ;
}
//======================
//凸多边形并的面积
double cross(point a,point b,point o);
struct polygon{
int n;
point a[5];
point& operator[](const int x){return a[x];}
void read(){
for(int i=0;i<n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
}
double area(){
double sum=cross(a[n-1],a[0]);
for(int i=0;i<n-1;++i)sum+=cross(a[i],a[i+1]);
return sum/2;
}
}po[510];
point operator-(point a,point b){
point px;px.x=b.x-a.x;px.y=b.y-a.y;
return px;
}
double cross(point a,point b){
return a.x*b.y-a.y*b.x;
}
double cross(point a,point b,point o){
double x1=a.x-o.x,y1=a.y-o.y,x2=b.x-o.x,y2=b.y-o.y;
return x1*y2-x2*y1;
}
double dot(point a,point b){
return a.x*b.x+a.y*b.y;
}
int sign(double x){
return x<-eps?-1:x>eps;
}
double seg(point a,point b,point c){
if(sign(a.y-b.y)==0)return (c.x-a.x)/(b.x-a.x);
else return (c.y-a.y)/(b.y-a.y);
}
pi b[4010];
double polyunion(int n){
double sum=0;
for(int i=0;i<n;++i)po[i][po[i].n]=po[i][0];
for(int i=0;i<n;++i)
for(int ii=0;ii<po[i].n;++ii){
int tot=0;
b[tot++]=mp(0.0,0);
b[tot++]=mp(1.0,0);
for(int j=0;j<n;++j){
if(i==j)continue;
for(int jj=0;jj<po[j].n;++jj){
int aa,bb;
aa=sign(cross(po[i][ii+1],po[j][jj],po[i][ii]));
bb=sign(cross(po[i][ii+1],po[j][jj+1],po[i][ii]));
if(aa==0&&bb==0){
if(dot(po[i][ii+1]-po[i][ii],po[j][jj+1]-po[j][jj])>0&&j<i){
b[tot++]=mp(seg(po[i][ii],po[i][ii+1],po[j][jj]),1);
b[tot++]=mp(seg(po[i][ii],po[i][ii+1],po[j][jj+1]),-1);
}
}
else if(aa<0&&bb>=0){
double s1=cross(po[i][ii],po[j][jj+1],po[j][jj]),s2=s1+cross(po[j][jj+1],po[i][ii+1],po[j][jj]);
b[tot++]=mp(s1/s2,-1);
}
else if(aa>=0&&bb<0){
double s1=cross(po[i][ii],po[j][jj+1],po[j][jj]),s2=s1+cross(po[j][jj+1],po[i][ii+1],po[j][jj]);
b[tot++]=mp(s1/s2,1);
}
}
}
sort(b,b+tot);
double last,now,s=0,co;
last=min(max(b[0].first,0.0),1.0);
co=b[0].second;
for(int j=1;j<tot;++j){
now=min(max(b[j].first,0.0),1.0);
if(!co)s+=now-last;
co+=b[j].second;
last=now;
}
sum+=cross(po[i][ii],po[i][ii+1])*s;
}
return sum/2;
}
//========================================
//两直线交点
point intersection(point u1,point u2,point v1,point v2){
point ret=u1;
double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
ret.x+=(u2.x-u1.x)*t;
ret.y+=(u2.y-u1.y)*t;
return ret;
}
//计算直线与圆的交点可用这个函数后判点是否在线段上
void intersection_line_circle(point c,double r,point l1,point l2,point& p1,point& p2){
point p=c;
double t;
p.x+=l1.y-l2.y;
p.y+=l2.x-l1.x;
p=intersection(p,c,l1,l2);
t=sqrt(r*r-dist(p,c)*dist(p,c))/dist(l1,l2);
//it's xiangqie in this problem, so p1=p2=p and return ;
p1 = p2 = p;
return ;
p1.x=p.x+(l2.x-l1.x)*t;
p1.y=p.y+(l2.y-l1.y)*t;
p2.x=p.x-(l2.x-l1.x)*t;
p2.y=p.y-(l2.y-l1.y)*t;
}
void solve_qua(double a,double b,double c,double &k0,double &k1){
if (a==0){
k0 = k1 = -c/b;
return ;
}
k0 = (-b+sqrt(b*b-4*a*c))/a/2;
k1 = (-b-sqrt(b*b-4*a*c))/a/2;
}
//计算圆外点和圆的切线交点 先计算斜率
int point_lineto_circle(double x0,double y0,double x1,double y1,double R,
point inter[]){
double a = x0-x1,c = y1-y0,k0,k1;
solve_qua(a*a-R*R,2*a*c,c*c-R*R,k0,k1);
// printf("%lf %lf\n",k0,k1);
point one,two,circle;
circle.x = x1,circle.y = y1;
one.x = x0,one.y = y0;
two.x = x0+100,two.y = k0*100+y0;
intersection_line_circle(circle,R,one,two,inter[0],inter[0]);
if (k0==k1)
two.x = x0,two.y = one.y+1;
else two.x = x0+100,two.y = k1*100+y0;
intersection_line_circle(circle,R,one,two,inter[1],inter[1]);
return 2;
}
/*=====================================
* 最近点对，归并
*/
void Min_dis(int L,int R){
if (L>=R) return ;
if (L+1==R) {
ans=min(ans,dist(p[L],p[R]));
return ;
}
int mid = L+R>>1,i,j;
Min_dis(L,mid),Min_dis(mid+1,R);
int t = 0;
for (i=L;i<=R;i++)
if (fabs(p[i].x-p[mid].x)<=ans)
q[t++] = i;
sort(q,q+t,cmp);
for (i=0;i<t;i++)
for (j=i+1;j<t;j++)
if (p[q[j]].y-p[q[i]].y>=ans) break;
else {
ans = min(ans,dist(p[q[i]],p[q[j]]));
}
}
/*
* 最小外接圆，随机增量，i 0>N j:0>i k:0>j
*/
point c;
c.x = 0,c.y = 0,c.r = 0;
for (i=0;i<N;i++)
if (dist(c,p[i])>c.r+eps){
c = p[i];
c.r = 0;
for (j=0;j<i;j++)
if (dist(c,p[j])>c.r+eps){
c.x = (p[i].x+p[j].x)/2;
c.y = (p[i].y+p[j].y)/2;
c.r = dist(p[i],p[j])/2;
for (k=0;k<j;k++)
if (dist(c,p[k])>c.r+eps){
c = calc(p[i].x-p[j].x,p[i].y-p[j].y,-(p[i].x-p[j].x)*(p[i].x+p[j].x)/2-(p[i].y-p[j].y)*(p[i].y+p[j].y)/2,
p[i].x-p[k].x,p[i].y-p[k].y,-(p[i].x-p[k].x)*(p[i].x+p[k].x)/2-(p[i].y-p[k].y)*(p[i].y+p[k].y)/2);
c.r = dist(c,p[i]);
}
}
}
printf("%.2f %.2f %.2f\n",c.x,c.y,c.r);
/*===============================================================
* 求N个圆相交形成的弧状区域
* 调试中修正的问题：
* 0. 注意输入需要抱着任意两圆间是相交关系，需要预先去除包含关系的大圆
* 1. >90度角用中点求内积相加得到
* 2. 区间必须记录后一起搞，可以离散化、扫描线
* 3. 注意去除0长度的区间，会影响最后结果计算。
*
* 20120815 contest4 I UVA Encircling circles.
*/
Point intersection(const Point & u1, const Point & u2, const Point & v1, const Point & v2) {
Point ret = u1;
double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) / ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
ret.x += (u2.x - u1.x) * t;
ret.y += (u2.y - u1.y) * t;
return ret;
}
//计算直线与圆的交点, 保证直线与圆有交点
//计算线段与圆的交点可用这个函数后判点是否在线段上
void intersectionLineCircle(const Point & c, double r, const Point & l1, const Point & l2, Point & p1, Point & p2) {
Point p = c;
p.x += l1.y - l2.y;
p.y += l2.x - l1.x;
p = intersection(p, c, l1, l2);
double t = sqrt(r * r - dis(p, c) * dis(p, c)) / dis(l1, l2);
p1.x = p.x + (l2.x - l1.x) * t;
p1.y = p.y + (l2.y - l1.y) * t;
p2.x = p.x - (l2.x - l1.x) * t;
p2.y = p.y - (l2.y - l1.y) * t;
}
//计算圆与圆的交点, 保证圆与圆有交点, 圆心不重合
void intersectionCircleCircle(const Point & c1, double r1, const Point & c2, double r2, Point & p1, Point & p2) {
Point u, v;
double t = (1 + (r1 * r1 - r2 * r2) / dis(c1, c2) / dis(c1, c2)) / 2;
u.x = c1.x + (c2.x - c1.x) * t;
u.y = c1.y + (c2.y - c1.y) * t;
v.x = u.x + c1.y - c2.y;
v.y = u.y - c1.x + c2.x;
//printf("%lf %lf %lf %lf %lf %lf %lf\n",c1.x,c1.y,r1,u.x,u.y,v.x,v.y);
intersectionLineCircle(c1, r1, u, v, p1, p2);
}
//the 0,0-based vector (x0,y0) change angle, counterclockwize.
Point changedir(double x0,double y0,double A){
Point ret;
ret.x = x0*cos(A)-y0*sin(A);
ret.y = x0*sin(A)+y0*cos(A);
return ret;
}
typedef pair<double,double> PDD;
typedef pair<Point,int> PPI;
bool cmp(PPI A,PPI B){
if (zero(A.first.x-B.first.x)) return A.first.y<B.first.y;
return A.first.x<B.first.x;
}
vector<PPI> inter;
vector<PDD> sec[1000];
double ans,rad;
double pi = acos(-1.0);
vector<Point> cir;
Point C[1000];
void out(Point A){
printf("%lf %lf %lf out point \n",A.x,A.y,A.r);
}
vector<PDD> inv[1000];
double Num[1000];
int t,cnt[1000];
map<double,int> mat;
void do_interval(int N,int now){
// a fucked slow N^2 method to union intervals, luckly the N<=100
sec[now].clear();
int i,j,k;
t = 0;
for (i=0;i<N;cnt[i++] = 0)
for (j=0;j<inv[i].size();j++)
Num[t++] = inv[i][j].first,Num[t++] = inv[i][j].second;
sort(Num,Num+t);
t = unique(Num,Num+t)-Num;
mat.clear();
for (i=0;i<t;i++)
mat[Num[i]] = i+1,cnt[i+1] = 0;
for (i=0;i<N;i++)
for (j=0;j<inv[i].size();j++)
{
int a = mat[inv[i][j].first],b=mat[inv[i][j].second];
for (k=a;k<b;k++)
cnt[k]++;
}
for (i=1;i<=t;i++)
if (cnt[i]==N&&!zero(Num[i-1]-Num[i])){
sec[now].push_back(PDD(Num[i-1],Num[i]));
}
}
void circle_intersection(int N){
int i,j;
for (i=0;i<N;i++){
double l1 = -pi,l2=-pi,r1=pi,r2=pi;
Point p1,p2;
inv[i].clear();
inv[i].push_back(PDD(-pi,pi));
for( j=0;j<N;j++)
if (i!=j){
inv[j].clear();
intersectionCircleCircle(cir[i],cir[i].r,cir[j],cir[j].r,
p1,p2);
double a = atan2(p1.y-cir[i].y,p1.x-cir[i].x);
double b = atan2(p2.y-cir[i].y,p2.x-cir[i].x);
if (a<b) swap(a,b),swap(p1,p2);
// get the middle point of Arc b->a, check if contain in circle_j
Point mid = changedir(p2.x-cir[i].x,p2.y-cir[i].y,(a-b)/2);
mid.x+=cir[i].x;
mid.y+=cir[i].y;
if (dis(mid,cir[j])+EPS>cir[j].r){
//a->b is interval: big to small, split
inv[j].push_back(PDD(a,pi));
inv[j].push_back(PDD(-pi,b));
}else {
//b->a is interval: small to big
inv[j].push_back(PDD(b,a));
}
}
sec[i].clear();
//union the intervals of circle i ,get the finalize arc of i in UNION AREA
do_interval(N,i);
}
ans = 0;
inter.clear();
for (i=0;i<N;i++)
if (sec[i].size()>0){
for (j=0;j<sec[i].size();j++)
{
//b -> a is a final interval, is arc-mode value.
double a = sec[i][j].second;
double b = sec[i][j].first;
ans+=(a-b)*(cir[i].r+rad);
Point tmp = changedir(-cir[i].r,0,a+pi);
tmp.x+=cir[i].x;
tmp.y+=cir[i].y;
inter.push_back(PPI(tmp,i));
tmp = changedir(-cir[i].r,0,b+pi);
tmp.x+=cir[i].x;
tmp.y+=cir[i].y;
inter.push_back(PPI(tmp,i));
}
}
sort(inter.begin(),inter.end(),cmp);
for (i=0;i+1<inter.size();i++)
{
Point A = inter[i].first, B = inter[i+1].first;
if (zero(A.x-B.x)&&zero(A.y-B.y)&&inter[i].second!=inter[i+1].second){
int a = inter[i].second,b = inter[i+1].second;
//to get the angle >90, split to middle point and use dmult.
Point mid;
mid.x = (cir[a].x+cir[b].x)/2;
mid.y = (cir[a].y+cir[b].y)/2;
double cc = dmult(cir[a],mid,A)/dis(cir[a],A)/dis(mid,A);
cc = acos(cc);
double bb = dmult(mid,cir[b],A)/dis(mid,A)/dis(cir[b],A);
cc+=acos(bb);
ans+=cc*rad;
}
}
}
}}}组队赛中WA过的提交，原因，所犯的2B错误：
1. burnside，最后除的N必须是置换群的准确size
2. 圆交：>90度角用中点求内积相加得到
3. 圆交：区间必须记录后一起搞，可以离散化、扫描线
4. 圆交：必须去除0长度的区间，会影响最后结果计算。
5. 偷懒把mark清零写到for循环上，结果清零的个数是N不是T，太新手了！
6. 没考虑DEP[I]（火车发车时间）,一个读入变量在程序中没被用到也没发现，丢！！
7. 当你发现模型是NPC问题，说明一定有附加条件！
8. 因为枚举的k要经过k%N==0的检查，于是我干脆枚举k时for k=N ; ;k+=N，
但是tot/k可能%N==0没被枚举到！
9. 求一个边权全部为1的有向图最短路，用dijkastra卡到死，这不就是个BFS吗
10. 爽了把299，当中间过程跑出负权环但不能最终到达终点，则该无视之！
11. 用map作离散化，超时到死，按题目实际情况考虑有没有更高效的方法
12. 线段树也可以不下传，比如用它做矩形并的时候。
13. 数量少时多用容斥的技巧思考问题
14. 开数组时思考大小是否够用，开变量时思考是否够存
15. 虽然是SPJ题 输出顺序有时也有规定
16. 向量旋转，WA到死，eps大到1e-5后AC
17. 用扫描线做计算几何时，未清晰考虑共线事件，
将弧度大小判断改成队列位置判断是否穿越-pi线，AC
18. 做几何题物理题的时候，看清楚各个输入数据的单位是什么！
19. 位压一个10位的数字，用while(k)WA到死，在有前置0的时候
20. DFA判相似的时候（以及类似图论题），应该无视不能到达danger点的那些结点！
个人选拔赛中WA过的提交，2B错误：
1. 有-操作，记得+mod)%mod
2. 2亿的数组也敢开，滚起啊
3. 次奥，哈夫曼编码也能忘？？
4. 手贱用某函数是否返回-1判数据合法性，结果没设置函数默认返回值TLE到死
5. 手贱加输入特判，又没人肉对，改后AC
6. 写个BFS，mark都忘记清
7. 高精度自动机DP 位数没开足
8.
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct point{double x,y;};
struct line{point a,b;};
//计算dot product (P1-P0).(P2-P0)
double dmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y);
}
//计算cross product (P1-P0)x(P2-P0)
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double dist(point p1,point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
//判三点共线
int dots_inline(point p1,point p2,point p3){
return zero(xmult(p1,p2,p3));
}
//判点是否在线段上,包括端点
int dot_online_in(point p,line l){
return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps;
}
//判两点在线段同侧,点在线段上返回0
int same_side(point p1,point p2,line l){
return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;
}
//判两直线平行
int parallel(line u,line v){
return zero((u.a.x-u.b.x)*(v.a.y-v.b.y)-(v.a.x-v.b.x)*(u.a.y-u.b.y));
}
//判两线段相交,包括端点和部分重合
int intersect_in(line u,line v){
if (!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b))
return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);
return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u);
}
//线段交点请另外判线段相交(同时还是要判断是否平行!)
point intersection(line u,line v){
point ret=u.a;
double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))
/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
ret.x+=(u.b.x-u.a.x)*t;
ret.y+=(u.b.y-u.a.y)*t;
return ret;
}
//判断直线是否和线段相交
int str_line_seg_in(point p1,point p2,line v){
if (dots_inline(p1,p2,v.a)||dots_inline(p1,p2,v.b)) return true;
line u;
u.a = p1,u.b = p2;
return !same_side(v.a,v.b,u);
}
//两条不相交线段间的最短距离
double seg_dist(point a0,point a1,point b0,point b1){
double ans = dist(a0,b0),tmp;
checkmin(ans,dist(a0,b1));
checkmin(ans,dist(a1,b0));
checkmin(ans,dist(a1,b1));
if (dist(b0,b1)>0){
if (dmult(b0,b1,b0,a0)>=0&&dmult(b1,b0,b1,a0)>=0){
tmp = xmult(b0,b1,b0,a0)/dist(b0,b1);
checkmin(ans,fabs(tmp));
}
if (dmult(b0,b1,b0,a1)>=0&&dmult(b1,b0,b1,a1)>=0){
tmp = xmult(b0,b1,b0,a1)/dist(b0,b1);
checkmin(ans,fabs(tmp));
}
}
if (dist(a0,a1)>0){
if (dmult(a0,a1,a0,b0)>=0&&dmult(a1,a0,a1,b0)>=0){
tmp = xmult(a0,a1,a0,b0)/dist(a0,a1);
checkmin(ans,fabs(tmp));
}
if (dmult(a0,a1,a0,b1)>=0&&dmult(a1,a0,a1,b1)>=0){
tmp = xmult(a0,a1,a0,b1)/dist(a0,a1);
checkmin(ans,fabs(tmp));
}
}
return ans;
}
//凸包可解决问题系列，旋转卡壳
//计算凸包，共线点是否保留修改>=0
bool cmp(point a,point b){
return a.y<b.y||(a.y==b.y&&a.x<b.x);
}
void calc(int N){
int i,cnt ;
double xa;
sort(P,P+N,cmp);
cnt = 0;
Q[cnt++] = 0;
for (i=1;i<N;)
if (cnt==1||xmult(P[Q[cnt-1]],P[i],P[Q[cnt-2]])>=0)
Q[cnt++] = i++;
else cnt--;
int top = cnt;
for (i=N-2;i>=0;)
if (cnt==top||xmult(P[Q[cnt-1]],P[i],P[Q[cnt-2]])>=0)
Q[cnt++] = i--;
else cnt--;
return ;
//旋转卡壳求最远点对
Q[cnt] = Q[1];
ans = 0;
for (i=0,j=top-1;i<top&&j<cnt;){
ans = max(ans,sqr(P[Q[i]].x-P[Q[j]].x)+sqr(P[Q[i]].y-P[Q[j]].y));
if (xmult(P[Q[i]],P[Q[i+1]],P[Q[j]],P[Q[j+1]])<0) i++;
else j++;
}
//旋转卡壳求两凸包间最短距离，需要seg_dist函数
sort(A,A+N,cmp);
int n1 = getQ(N,A,Q1);
sort(B,B+M,cmp2);
int n2 = getQ(M,B,Q2);
ans = dist(A[0],B[0]);
for (i=0,j=0;i<n1&&j<n2;){
checkmin(ans, seg_dist(A[Q1[i]],A[Q1[i+1]],B[Q2[j]],B[Q2[j+1]]));
if (xmult(A[Q1[i]],A[Q1[i+1]],B[Q2[j]],B[Q2[j+1]])<0) i++;
else j++;
}
//============================
//旋转卡壳求最小面积外接矩形
double lx = 1e100,rx = -1e100;
int j,L,R;
for (i=0;i<cnt;i++){
if (lx>P[Q[i]].x) lx = P[Q[i]].x,L = i;
if (rx<P[Q[i]].x) rx = P[Q[i]].x,R = i;
}
for (i=0,j=top-1;i<cnt-1;i++){
while(xmult(P[Q[i]],P[Q[i+1]],P[Q[j]],P[Q[j+1]])>0)
{
j++;
if (j==cnt-1) j = 0;
}
while(dmult(P[Q[i]],P[Q[i+1]],P[Q[L]],P[Q[L+1]])<0){
L++;
if (L==cnt-1) L = 0;
}
while(dmult(P[Q[i]],P[Q[i+1]],P[Q[R]],P[Q[R+1]])>0){
R++;
if (R==cnt-1) R = 0;
}
ans = min(ans, fabs(xmult(P[Q[i]],P[Q[i+1]],P[Q[i]],P[Q[j]])
*(dmult(P[Q[i]],P[Q[i+1]],P[Q[i]],P[Q[R]])
-dmult(P[Q[i]],P[Q[i+1]],P[Q[i]],P[Q[L]]))
/distsqr(P[Q[i]],P[Q[i+1]])));
}
return ;
/*
* 旋转卡壳求点集组成最大三角形面积
* 不断调整卡壳线，不能调整时手动将第一条线前移
* POJ数据过水，attention the code
*/
int tot = polygen();
i= 0 ,j = 1,k =2;
double ans = 0;
while(1){
int bi = i,bj = j,bk = k;
while(k<tot&&fabs(xmult(Q[i],Q[j],Q[k]))<fabs(xmult(Q[i],Q[j],Q[k+1])))
k++;
while(j<k&&fabs(xmult(Q[i],Q[j],Q[k]))<fabs(xmult(Q[i],Q[j+1],Q[k])))
j++;
while(i<j&&fabs(xmult(Q[i],Q[j],Q[k]))<fabs(xmult(Q[i+1],Q[j],Q[k])))
i++;
ans = max(ans,xmult(Q[i],Q[j],Q[k]));
if (bi==i&&bj==j&&bk==k)
k++;
if (k==tot) break;
}
printf("%.2lf\n",ans/2);
return ;
}
//======================
//凸多边形并的面积
double cross(point a,point b,point o);
struct polygon{
int n;
point a[5];
point& operator[](const int x){return a[x];}
void read(){
for(int i=0;i<n;++i)
scanf("%lf%lf",&a[i].x,&a[i].y);
}
double area(){
double sum=cross(a[n-1],a[0]);
for(int i=0;i<n-1;++i)sum+=cross(a[i],a[i+1]);
return sum/2;
}
}po[510];
point operator-(point a,point b){
point px;px.x=b.x-a.x;px.y=b.y-a.y;
return px;
}
double cross(point a,point b){
return a.x*b.y-a.y*b.x;
}
double cross(point a,point b,point o){
double x1=a.x-o.x,y1=a.y-o.y,x2=b.x-o.x,y2=b.y-o.y;
return x1*y2-x2*y1;
}
double dot(point a,point b){
return a.x*b.x+a.y*b.y;
}
int sign(double x){
return x<-eps?-1:x>eps;
}
double seg(point a,point b,point c){
if(sign(a.y-b.y)==0)return (c.x-a.x)/(b.x-a.x);
else return (c.y-a.y)/(b.y-a.y);
}
pi b[4010];
double polyunion(int n){
double sum=0;
for(int i=0;i<n;++i)po[i][po[i].n]=po[i][0];
for(int i=0;i<n;++i)
for(int ii=0;ii<po[i].n;++ii){
int tot=0;
b[tot++]=mp(0.0,0);
b[tot++]=mp(1.0,0);
for(int j=0;j<n;++j){
if(i==j)continue;
for(int jj=0;jj<po[j].n;++jj){
int aa,bb;
aa=sign(cross(po[i][ii+1],po[j][jj],po[i][ii]));
bb=sign(cross(po[i][ii+1],po[j][jj+1],po[i][ii]));
if(aa==0&&bb==0){
if(dot(po[i][ii+1]-po[i][ii],po[j][jj+1]-po[j][jj])>0&&j<i){
b[tot++]=mp(seg(po[i][ii],po[i][ii+1],po[j][jj]),1);
b[tot++]=mp(seg(po[i][ii],po[i][ii+1],po[j][jj+1]),-1);
}
}
else if(aa<0&&bb>=0){
double s1=cross(po[i][ii],po[j][jj+1],po[j][jj]),s2=s1+cross(po[j][jj+1],po[i][ii+1],po[j][jj]);
b[tot++]=mp(s1/s2,-1);
}
else if(aa>=0&&bb<0){
double s1=cross(po[i][ii],po[j][jj+1],po[j][jj]),s2=s1+cross(po[j][jj+1],po[i][ii+1],po[j][jj]);
b[tot++]=mp(s1/s2,1);
}
}
}
sort(b,b+tot);
double last,now,s=0,co;
last=min(max(b[0].first,0.0),1.0);
co=b[0].second;
for(int j=1;j<tot;++j){
now=min(max(b[j].first,0.0),1.0);
if(!co)s+=now-last;
co+=b[j].second;
last=now;
}
sum+=cross(po[i][ii],po[i][ii+1])*s;
}
return sum/2;
}
//========================================
//两直线交点
point intersection(point u1,point u2,point v1,point v2){
point ret=u1;
double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
ret.x+=(u2.x-u1.x)*t;
ret.y+=(u2.y-u1.y)*t;
return ret;
}
//计算直线与圆的交点可用这个函数后判点是否在线段上
void intersection_line_circle(point c,double r,point l1,point l2,point& p1,point& p2){
point p=c;
double t;
p.x+=l1.y-l2.y;
p.y+=l2.x-l1.x;
p=intersection(p,c,l1,l2);
t=sqrt(r*r-dist(p,c)*dist(p,c))/dist(l1,l2);
//it's xiangqie in this problem, so p1=p2=p and return ;
p1 = p2 = p;
return ;
p1.x=p.x+(l2.x-l1.x)*t;
p1.y=p.y+(l2.y-l1.y)*t;
p2.x=p.x-(l2.x-l1.x)*t;
p2.y=p.y-(l2.y-l1.y)*t;
}
void solve_qua(double a,double b,double c,double &k0,double &k1){
if (a==0){
k0 = k1 = -c/b;
return ;
}
k0 = (-b+sqrt(b*b-4*a*c))/a/2;
k1 = (-b-sqrt(b*b-4*a*c))/a/2;
}
//计算圆外点和圆的切线交点 先计算斜率
int point_lineto_circle(double x0,double y0,double x1,double y1,double R,
point inter[]){
double a = x0-x1,c = y1-y0,k0,k1;
solve_qua(a*a-R*R,2*a*c,c*c-R*R,k0,k1);
// printf("%lf %lf\n",k0,k1);
point one,two,circle;
circle.x = x1,circle.y = y1;
one.x = x0,one.y = y0;
two.x = x0+100,two.y = k0*100+y0;
intersection_line_circle(circle,R,one,two,inter[0],inter[0]);
if (k0==k1)
two.x = x0,two.y = one.y+1;
else two.x = x0+100,two.y = k1*100+y0;
intersection_line_circle(circle,R,one,two,inter[1],inter[1]);
return 2;
}
/*=====================================
* 最近点对，归并
*/
void Min_dis(int L,int R){
if (L>=R) return ;
if (L+1==R) {
ans=min(ans,dist(p[L],p[R]));
return ;
}
int mid = L+R>>1,i,j;
Min_dis(L,mid),Min_dis(mid+1,R);
int t = 0;
for (i=L;i<=R;i++)
if (fabs(p[i].x-p[mid].x)<=ans)
q[t++] = i;
sort(q,q+t,cmp);
for (i=0;i<t;i++)
for (j=i+1;j<t;j++)
if (p[q[j]].y-p[q[i]].y>=ans) break;
else {
ans = min(ans,dist(p[q[i]],p[q[j]]));
}
}
/*
* 最小外接圆，随机增量，i 0>N j:0>i k:0>j
*/
point c;
c.x = 0,c.y = 0,c.r = 0;
for (i=0;i<N;i++)
if (dist(c,p[i])>c.r+eps){
c = p[i];
c.r = 0;
for (j=0;j<i;j++)
if (dist(c,p[j])>c.r+eps){
c.x = (p[i].x+p[j].x)/2;
c.y = (p[i].y+p[j].y)/2;
c.r = dist(p[i],p[j])/2;
for (k=0;k<j;k++)
if (dist(c,p[k])>c.r+eps){
c = calc(p[i].x-p[j].x,p[i].y-p[j].y,-(p[i].x-p[j].x)*(p[i].x+p[j].x)/2-(p[i].y-p[j].y)*(p[i].y+p[j].y)/2,
p[i].x-p[k].x,p[i].y-p[k].y,-(p[i].x-p[k].x)*(p[i].x+p[k].x)/2-(p[i].y-p[k].y)*(p[i].y+p[k].y)/2);
c.r = dist(c,p[i]);
}
}
}
printf("%.2f %.2f %.2f\n",c.x,c.y,c.r);
/*===============================================================
* 求N个圆相交形成的弧状区域
* 调试中修正的问题：
* 0. 注意输入需要抱着任意两圆间是相交关系，需要预先去除包含关系的大圆
* 1. >90度角用中点求内积相加得到
* 2. 区间必须记录后一起搞，可以离散化、扫描线
* 3. 注意去除0长度的区间，会影响最后结果计算。
*
* 20120815 contest4 I UVA Encircling circles.
*/
Point intersection(const Point & u1, const Point & u2, const Point & v1, const Point & v2) {
Point ret = u1;
double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y - v1.y) * (v1.x - v2.x)) / ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
ret.x += (u2.x - u1.x) * t;
ret.y += (u2.y - u1.y) * t;
return ret;
}
//计算直线与圆的交点, 保证直线与圆有交点
//计算线段与圆的交点可用这个函数后判点是否在线段上
void intersectionLineCircle(const Point & c, double r, const Point & l1, const Point & l2, Point & p1, Point & p2) {
Point p = c;
p.x += l1.y - l2.y;
p.y += l2.x - l1.x;
p = intersection(p, c, l1, l2);
double t = sqrt(r * r - dis(p, c) * dis(p, c)) / dis(l1, l2);
p1.x = p.x + (l2.x - l1.x) * t;
p1.y = p.y + (l2.y - l1.y) * t;
p2.x = p.x - (l2.x - l1.x) * t;
p2.y = p.y - (l2.y - l1.y) * t;
}
//计算圆与圆的交点, 保证圆与圆有交点, 圆心不重合
void intersectionCircleCircle(const Point & c1, double r1, const Point & c2, double r2, Point & p1, Point & p2) {
Point u, v;
double t = (1 + (r1 * r1 - r2 * r2) / dis(c1, c2) / dis(c1, c2)) / 2;
u.x = c1.x + (c2.x - c1.x) * t;
u.y = c1.y + (c2.y - c1.y) * t;
v.x = u.x + c1.y - c2.y;
v.y = u.y - c1.x + c2.x;
//printf("%lf %lf %lf %lf %lf %lf %lf\n",c1.x,c1.y,r1,u.x,u.y,v.x,v.y);
intersectionLineCircle(c1, r1, u, v, p1, p2);
}
//the 0,0-based vector (x0,y0) change angle, counterclockwize.
Point changedir(double x0,double y0,double A){
Point ret;
ret.x = x0*cos(A)-y0*sin(A);
ret.y = x0*sin(A)+y0*cos(A);
return ret;
}
typedef pair<double,double> PDD;
typedef pair<Point,int> PPI;
bool cmp(PPI A,PPI B){
if (zero(A.first.x-B.first.x)) return A.first.y<B.first.y;
return A.first.x<B.first.x;
}
vector<PPI> inter;
vector<PDD> sec[1000];
double ans,rad;
double pi = acos(-1.0);
vector<Point> cir;
Point C[1000];
void out(Point A){
printf("%lf %lf %lf out point \n",A.x,A.y,A.r);
}
vector<PDD> inv[1000];
double Num[1000];
int t,cnt[1000];
map<double,int> mat;
void do_interval(int N,int now){
// a fucked slow N^2 method to union intervals, luckly the N<=100
sec[now].clear();
int i,j,k;
t = 0;
for (i=0;i<N;cnt[i++] = 0)
for (j=0;j<inv[i].size();j++)
Num[t++] = inv[i][j].first,Num[t++] = inv[i][j].second;
sort(Num,Num+t);
t = unique(Num,Num+t)-Num;
mat.clear();
for (i=0;i<t;i++)
mat[Num[i]] = i+1,cnt[i+1] = 0;
for (i=0;i<N;i++)
for (j=0;j<inv[i].size();j++)
{
int a = mat[inv[i][j].first],b=mat[inv[i][j].second];
for (k=a;k<b;k++)
cnt[k]++;
}
for (i=1;i<=t;i++)
if (cnt[i]==N&&!zero(Num[i-1]-Num[i])){
sec[now].push_back(PDD(Num[i-1],Num[i]));
}
}
void circle_intersection(int N){
int i,j;
for (i=0;i<N;i++){
double l1 = -pi,l2=-pi,r1=pi,r2=pi;
Point p1,p2;
inv[i].clear();
inv[i].push_back(PDD(-pi,pi));
for( j=0;j<N;j++)
if (i!=j){
inv[j].clear();
intersectionCircleCircle(cir[i],cir[i].r,cir[j],cir[j].r,
p1,p2);
double a = atan2(p1.y-cir[i].y,p1.x-cir[i].x);
double b = atan2(p2.y-cir[i].y,p2.x-cir[i].x);
if (a<b) swap(a,b),swap(p1,p2);
// get the middle point of Arc b->a, check if contain in circle_j
Point mid = changedir(p2.x-cir[i].x,p2.y-cir[i].y,(a-b)/2);
mid.x+=cir[i].x;
mid.y+=cir[i].y;
if (dis(mid,cir[j])+EPS>cir[j].r){
//a->b is interval: big to small, split
inv[j].push_back(PDD(a,pi));
inv[j].push_back(PDD(-pi,b));
}else {
//b->a is interval: small to big
inv[j].push_back(PDD(b,a));
}
}
sec[i].clear();
//union the intervals of circle i ,get the finalize arc of i in UNION AREA
do_interval(N,i);
}
ans = 0;
inter.clear();
for (i=0;i<N;i++)
if (sec[i].size()>0){
for (j=0;j<sec[i].size();j++)
{
//b -> a is a final interval, is arc-mode value.
double a = sec[i][j].second;
double b = sec[i][j].first;
ans+=(a-b)*(cir[i].r+rad);
Point tmp = changedir(-cir[i].r,0,a+pi);
tmp.x+=cir[i].x;
tmp.y+=cir[i].y;
inter.push_back(PPI(tmp,i));
tmp = changedir(-cir[i].r,0,b+pi);
tmp.x+=cir[i].x;
tmp.y+=cir[i].y;
inter.push_back(PPI(tmp,i));
}
}
sort(inter.begin(),inter.end(),cmp);
for (i=0;i+1<inter.size();i++)
{
Point A = inter[i].first, B = inter[i+1].first;
if (zero(A.x-B.x)&&zero(A.y-B.y)&&inter[i].second!=inter[i+1].second){
int a = inter[i].second,b = inter[i+1].second;
//to get the angle >90, split to middle point and use dmult.
Point mid;
mid.x = (cir[a].x+cir[b].x)/2;
mid.y = (cir[a].y+cir[b].y)/2;
double cc = dmult(cir[a],mid,A)/dis(cir[a],A)/dis(mid,A);
cc = acos(cc);
double bb = dmult(mid,cir[b],A)/dis(mid,A)/dis(cir[b],A);
cc+=acos(bb);
ans+=cc*rad;
}
}
}
附加文件
- 屏幕快照 2012-08-07 下午10.24.56.png by prowindy
- mj_bg.png by prowindy
- pku_2069最小包围球.txt by prowindy
- pku_3384(半平面交）.txt by prowindy
- 三维凸包3.txt by prowindy
- 长方体上两点间的最短距离.cpp by prowindy
- 笛卡尔树.cpp by prowindy
- pku3384半平面交.txt by prowindy
- 统计一个平面图中所有边数为k的面的个数.cpp by prowindy
- 多边形费马点.cpp by prowindy
- 组成凸包的期望.cpp by prowindy
- 点对简单多边形的张角.cpp by prowindy
- 梯形剖分o(n^3).txt by prowindy