题解clj大神有了就不放了
一道非常好的题目，只是调试能死人罢了
注意要点:
1.此时的极角排序必须加上象限的判断不然会出错(重要!)
2.注意每次point数组必须清空而不能复用因为编号乱了
3.以后数组开到原来的4倍左右防止因数组开小而出错
4.使用long long类型可以有效避免精度误差
5.以后碰到这种题我就写一个O(n3)的暴力，因为这题数据很良心是可以过的，而且我考场上几乎100%不能调试成功
下面版本复杂度为O(n2logn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | #include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>using namespace std;const int N=4005;const double eps=1e-17;int n,cnt,ind[N];double ans;struct Point{long long x,y;int id;Point(){}Point(long long _x,long long _y){x=_x;y=_y;}friend inline Point operator+(const Point &A,const Point &B){return Point(A.x+B.x,A.y+B.y);}friend inline Point operator-(const Point &A,const Point &B){return Point(A.x-B.x,A.y-B.y);}friend inline long long operator*(const Point &A,const Point &B){return A.x*B.y-A.y*B.x;}friend inline bool operator==(const Point &A,const Point &B){return A.x==B.x && A.y==B.y;}}ChosenPoint,point[N<<1];inline int Check(Point A){if(A.x-ChosenPoint.x>0 && A.y-ChosenPoint.y>=0)return 0;if(A.x-ChosenPoint.x<=0 && A.y-ChosenPoint.y>0)return 1;if(A.x-ChosenPoint.x<0 && A.y-ChosenPoint.y<=0)return 2;return 3;}inline int Dist2(const Point &A,const Point &B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}inline bool cmp(const Point &A,const Point &B){int x=Check(A),y=Check(B);if(x!=y)return x<y;return (A-ChosenPoint)*(B-ChosenPoint)>=0;}inline bool OnRight(const Point &A,const Point &B,const Point &C){return (B-A)*(C-A)>=0;}struct Pair_Points{Point A,B;}poi[N];int main(){freopen("1225.in","r",stdin);freopen("1225.out","w",stdout);scanf("%d",&n);if(n<3){puts("0.000000");return 0;}for(int i=1;i<=n;i++)scanf("%lld %lld %lld %lld",&poi[i].A.x,&poi[i].A.y,&poi[i].B.x,&poi[i].B.y);for(int i=1;i<=n;i++){ ChosenPoint=poi[i].A; cnt=0; for(int j=1;j<=n;j++){ if(i==j)continue; point[++cnt]=poi[j].A;point[cnt].id=j;point[++cnt]=poi[j].B;point[cnt].id=j; } sort(point+1,point+cnt+1,cmp); memset(ind,0,sizeof(ind)); int cntx[3]={n-1},pos=1; for(int j=cnt+1;j<=2*cnt;j++)point[j]=point[j-cnt]; for(int j=1;j<=cnt;j++){ while(pos<j+cnt && OnRight(ChosenPoint,point[j],point[pos])){ ind[point[pos].id]++; cntx[ind[point[pos].id]]++; cntx[ind[point[pos].id]-1]--; pos++; } //printf("%d %d %d %d\n", pos, cntx[0], cntx[1], cntx[2]); if(cntx[1]+cntx[2]==n-1){ double afk=0.125; if(ind[point[j].id]==1)afk/=pow(2,cntx[1]-1); else afk/=pow(2,cntx[1]); ans+=afk*(ChosenPoint*point[j]); } ind[point[j].id]--; cntx[ind[point[j].id]]++; cntx[ind[point[j].id]+1]--; }}for(int i=1;i<=n;i++){ ChosenPoint=poi[i].B; cnt=0; for(int j=1;j<=n;j++){ if(i==j)continue; point[++cnt]=poi[j].A;point[cnt].id=j;point[++cnt]=poi[j].B;point[cnt].id=j; } sort(point+1,point+cnt+1,cmp); memset(ind,0,sizeof(ind)); int cntx[3]={n-1},pos=1; for(int j=cnt+1;j<=2*cnt;j++)point[j]=point[j-cnt]; for(int j=1;j<=cnt;j++){ while(pos<j+cnt && OnRight(ChosenPoint,point[j],point[pos])){ ind[point[pos].id]++; cntx[ind[point[pos].id]]++; cntx[ind[point[pos].id]-1]--; pos++; } //printf("%d %d %d %d\n", pos, cntx[0], cntx[1], cntx[2]); if(cntx[1]+cntx[2]==n-1){ double afk=0.125; if(ind[point[j].id]==1)afk/=pow(2,cntx[1]-1); else afk/=pow(2,cntx[1]); ans+=afk*(ChosenPoint*point[j]); } ind[point[j].id]--; cntx[ind[point[j].id]]++; cntx[ind[point[j].id]+1]--; }}printf("%.17lf\n",ans);return 0;} |
评论 (0)
