[校内训练20_01

[校内训练20_01_20]ABC

1.问有多少个大小为N的无标号无根树，直径恰好为L。$N,L leq 200$
2.问一个竞赛图中有多少个长度为3、4、5的环。$N leq 2000$
3.给出一些直线和单个点A，问这些直线的交点与A最近的M个距离之和为多少。$N leq 50000,M leq 10^7$。保证不存在两个交点与点A的距离相同。
二分圆的半径，算交点个数，最后统计答案用并查集。
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long double ld;
  4 const int maxn=1E5+5;
  5 const ld eps=1E-9;
  6 const ld pi=acos(-1);
  7 const ld inf=1E12;
  8 int n,m;
  9 ld X,Y;
 10 struct pt
 11 {
 12     ld x,y;
 13     pt(ld a=0,ld b=0):x(a),y(b){}
 14     pt operator+(const pt&A){return pt(x+A.x,y+A.y);}
 15     pt operator-(const pt&A){return pt(x-A.x,y-A.y);}
 16     pt operator*(const ld&d){return pt(x*d,y*d);}
 17     pt operator/(const ld&d){return pt(x/d,y/d);}
 18     ld operator*(const pt&A){return x*A.y-y*A.x;}
 19     inline void out()
 20     {
 21         cout<<"("<<x<<","<<y<<")";
 22     }
 23 }O;
 24 struct line
 25 {
 26     pt A,B;
 27     line(pt a=pt(),pt b=pt()):A(a),B(b){}
 28 }a[maxn];
 29 struct BIT
 30 {
 31     int tot;
 32     int t[maxn];
 33     inline void clear(){memset(t,0,sizeof(t));}
 34     inline int lowbit(int x){return x&(-x);}
 35     inline int ask(int x){int sum=0;while(x){sum+=t[x];x-=lowbit(x);}return sum;}
 36     inline void add(int x,int y){while(x<=tot){t[x]+=y;x+=lowbit(x);}}
 37 }B;
 38 int size;
 39 struct info
 40 {
 41     int type,num;
 42     ld x;
 43     info(int a=0,int b=0,ld c=0):type(a),num(b),x(c){}
 44     bool operator<(const info&A)const
 45     {
 46         return x<A.x;
 47     }
 48 }tmp[maxn];
 49 inline pt intersection(line a,line b)
 50 {
 51     pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A;
 52     if(abs(A*B)<=eps)
 53         return pt(inf,inf);
 54     ld d=-(B*C)/(B*A);
 55     return b.A+A*d;
 56 }
 57 inline pt T(pt A)
 58 {
 59     swap(A.x,A.y);
 60     A.y=-A.y;
 61     return A;
 62 }
 63 inline pt perpendicular(pt A,line x)
 64 {
 65     pt B=T(x.B-x.A)+A;
 66     return intersection(line(A,B),x);
 67 }
 68 inline ld s(ld x)
 69 {
 70     return x*x;
 71 }
 72 int rk[2][maxn];
 73 inline bool check(ld r)
 74 {
 75     size=0;
 76     for(int i=1;i<=n;++i)
 77     {
 78         pt A=perpendicular(O,a[i]);
 79         ld x=s(A.x-O.x)+s(A.y-O.y);
 80         if(x>=r*r+eps)
 81             continue;
 82         pt d=T((O-A)*sqrt(r*r/x-1));
 83         pt P1=A+d,P2=A-d;
 84         ld x1=atan2(P1.y-O.y,P1.x-O.x);
 85         ld x2=atan2(P2.y-O.y,P2.x-O.x);
 86         if(!(x1<0)&&!(x1>=0))
 87         {
 88             x1=atan2(a[i].A.y-a[i].B.y,a[i].A.x-a[i].B.x);
 89             if(x1<0)
 90                 x2=x1+pi;
 91             else
 92                 x2=x1-pi;
 93         }
 94         if(x1>x2)
 95             swap(x1,x2);
 96         tmp[++size]=info(0,i,x1);
 97         tmp[++size]=info(1,i,x2);
 98     }
 99     sort(tmp+1,tmp+size+1);
100     for(int i=1;i<=size;++i)
101         rk[tmp[i].type][tmp[i].num]=i;
102     B.clear();
103     B.tot=size;
104     long long sum=0;
105     for(int i=1;i<=size;++i)
106     {
107         if(tmp[i].type==0)
108             B.add(i,1);
109         else
110         {
111             sum+=B.ask(i-1)-B.ask(rk[0][tmp[i].num]);
112             B.add(rk[0][tmp[i].num],-1);
113         }
114     }
115     return sum>=m;
116 }
117 int fa[maxn];
118 int find(int x)
119 {
120     return x==fa[x]?x:fa[x]=find(fa[x]);
121 }
122 bool ok[maxn];
123 inline ld dis(pt A,pt B)
124 {
125     return sqrt(s(A.x-B.x)+s(A.y-B.y));
126 }
127 inline ld get(ld r)
128 {
129     size=0;
130     for(int i=1;i<=n;++i)
131     {
132         pt A=perpendicular(O,a[i]);
133         ld x=s(A.x-O.x)+s(A.y-O.y);
134         if(x>=r*r+eps)
135             continue;
136         ok[i]=1;
137         pt d=T((O-A)*sqrt(r*r/x-1));
138         pt P1=A+d,P2=A-d;
139         ld x1=atan2(P1.y-O.y,P1.x-O.x);
140         ld x2=atan2(P2.y-O.y,P2.x-O.x);
141         if(abs(O.x-A.x)<=eps&&abs(O.y-A.y)<=eps)
142         {
143             x1=atan2(a[i].A.y-a[i].B.y,a[i].A.x-a[i].B.x);
144             if(x1<0)
145                 x2=x1+pi;
146             else
147                 x2=x1-pi;
148         }
149         if(x1>x2)
150             swap(x1,x2);
151         tmp[++size]=info(0,i,x1);
152         tmp[++size]=info(1,i,x2);
153     }
154     sort(tmp+1,tmp+size+1);
155     for(int i=1;i<=n;++i)
156     for(int i=1;i<=size;++i)
157         fa[i]=rk[tmp[i].type][tmp[i].num]=i;
158     fa[size+1]=size+1;
159     ld sum=0;
160     for(int i=1;i<=size;++i)
161         if(tmp[i].type)
162         {
163             int l=rk[0][tmp[i].num];
164             fa[l]=l+1,fa[i]=i+1;
165             while((l=find(l))<i)
166             {
167                 pt A=intersection(a[tmp[l].num],a[tmp[i].num]);
168                 sum+=dis(intersection(a[tmp[l].num],a[tmp[i].num]),O);
169                 ++l;
170             }
171         }
172     return sum;
173 }
174 inline int R()
175 {
176     return rand()%10000-5000;
177 }
178 int main()
179 {
180 //    freopen("stigmata.in","r",stdin);
181 //    freopen("stigmata.out","w",stdout);
182     ios::sync_with_stdio(false);
183     cin>>n>>X>>Y>>m;
184     X/=1000,Y/=1000;
185     for(int i=1;i<=n;++i)
186     {
187         ld x,y;
188         cin>>x>>y;
189         x/=1000,y/=1000;
190         a[i]=line(pt(0,y),pt(1000,1000*x+y));
191     }
192     O=pt(X,Y);
193     ld L=0,R=10000,mid;
194     while(abs(L-R)>0.00000001)
195     {
196         mid=(L+R)/2;
197         if(check(mid))
198             R=mid;
199         else
200             L=mid;
201     }
202     cout<<fixed<<setprecision(7)<<get(R)<<endl;
203     return 0;
204 }
View Code