DP+卡常数+高精度/  计算几何+二分+判区间交/  凸包

---

　　首先感谢徐老师的慷慨，让蒟蒻有幸膜拜了学军的神题。祝NOI2015圆满成功

　　同时膜拜碾压了蒟蒻的众神QAQ

填填填

　　我的DP比较逗比……（当时看到其他大神有更加优秀的做法）

　　f[i][j]表示前 i 个数，第一行填了 j 个的方案数，那么如果 i 并没有固定位置，f[i][j]=f[i-1][j]+f[i-1][j-1];即 i 这个数放在第一行或是第二行。。。（废话）

　　如果 i 固定的位置是第一行（1，y），那么f[i]中只有f[i][y]=f[i-1][y-1];（这个数一定放在第一行）

　　如果 i 固定的位置是第二行（2，y），那么f[i]中只有f[i][i-y]=f[i-1][i-y];（一定放在第二行）

　　这个DP是会爆空间的，但是我们发现f[i]只跟f[i-1]有关，所以滚动数组优化一下就好了……（我一开始还在蛋疼高精度的数组开不下）

　　我比较傻逼，不知道XJOI是不能用#ifndef ONLINE_JUDGE的，所以第一题没删文件操作……爆零滚粗了，删掉后是70分，两RE四TLE。

　　然后开始了漫漫卡常之路……比如高精从int压9位改成long long压17位，高精加的过程用指针实现（Orz Davidlee1999）

　　RE的那两个点是怎么回事呢？因为如果 i 固定的位置是第二行的时候，i-y可能会越界！（也就是无法得到一组合法解）那么这个时候我需要特判一下……

 1 //XJOI test7 A
 2 #include<ctime>
 3 #include<vector>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define repi,n) forint i=0;i<n;++i)
10 #define Fi,j,n) forint i=j;i<=n;++i)
11 #define Di,j,n) forint i=j;i>=n;--i)
12 #define pb push_back
13 using namespace std;
14 inline int getint){
15     int v=0,sign=1; char ch=getchar);
16     whilech<'0'||ch>'9'){ if ch=='-') sign=-1; ch=getchar);}
17     whilech>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar);}
18     return v*sign;
19 }
20 const int N=4010,INF=~0u>>2;
21 typedef long long LL;
22 /******************tamplate*********************/
23   
24 struct bint{
25     LL a[50],l;
26     bint){l=0;memseta,0,sizeof a);}
27     LL& operator [] int x){return a[x];}
28 }f[2][N];
29 const LL Limit=100000000000000000LL;
30 void printbint a){
31     printf"%lld",a[a.l]);
32     Di,a.l-1,1) printf"%017lld",a[i]);
33     puts"");
34 }
35 bint operator + bint a,bint &b){
36     LL *it1=a.a+1,*it2=b.a+1;
37     int l=maxa.l,b.l);
38     Fi,1,l){
39         *it1+=*it2;
40         it1++; it2++;
41     }
42     it1=a.a+1,it2=a.a+2;
43     Fi,1,l){
44         if *it1>=Limit) *it1-=Limit,*it2)++;
45         it1++; it2++;
46     }
47     if a[l+1]>0) a.l=l+1; else a.l=l;
48     return a;
49 }
50 int n,v[3][N];
51 typedef pair<int,int> pii;
52 #define mp make_pair
53 #define fi first
54 #define se second
55 pii pos[N];
56   
57   
58 int main){
59 //  time_t start,end; start=clock);
60     n=getint);
61     Fi,1,2) Fj,1,n){
62         v[i][j]=getint);
63         if v[i][j]) pos[v[i][j]]=mpi,j);
64     }
65     f[0][0].l=f[0][0][1]=1;
66     Fi,1,2*n){
67         int now=i&1;
68         if pos[i].fi==1){
69             int j=pos[i].se;
70             f[now][j]=f[now^1][j-1];
71         }else if pos[i].fi==2){
72             int j=i-pos[i].se;
73             if j<=0){printf"0
"); return 0;}
74             f[now][j]=f[now^1][j];
75         }else{
76             Fj,i+1)/2,mini,n)){
77                  f[now][j]=f[now^1][j-1]+f[now^1][j];
78 //                 f[now][j]=f[now][j]+f[now^1][j];
79             }
80         }
81         Fj,i/2,mini-1,n)) f[now^1][j]=bint);
82     }
83     printf[0][n]);
84 /*  end=clock);
85     cout <<"start : "<<start<<endl;
86     cout <<"end : "<<end<<endl;
87     cout <<"time : "<<doubleend-start)/CLOCKS_PER_SEC<<endl;
88 */  return 0;
89 }

View Code

线线线

　　计算几何QAQ

　　这题……倒是很容易想到可以二分这个dist，那么对于$S$中的每一个点，以它为圆心，dist为半径画一个圆，只要直线与这个圆的交集不为空那么这个圆就可以满足了……那么满足条件的直线所组成的明显是个扇形（只看一侧的话，因为是直线，两边加起来是对称的两个扇形）。

　　然而我并不会算扇形的交……（由此可见多么傻逼）

　　想到这里我就弃疗了……没有写……连暴力都不会……

　　然而其实并不用算扇形交= =因为这个直线不是过定点嘛，那么所谓扇形……其实就是极角对应的区间罢了！所以其实就是求区间交！找是否有一段被n个区间覆盖即可……注意由于是直线，所以反向的那一边穿过去也可以……所以一个$S$中的点应该是对应两个区间！（Orz zld神犇）

　　进入区间+1，离开区间-1，每个区间的左右端点都视为一个事件，排序一下，看是否某一时刻前缀和为n即可。

 1 //XJOI test7 B
 2 //Orz zld大爷
 3 #include<vector>
 4 #include<cmath>
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<cstdlib>
 8 #include<iostream>
 9 #include<algorithm>
10 #define repi,n) forint i=0;i<n;++i)
11 #define Fi,j,n) forint i=j;i<=n;++i)
12 #define Di,j,n) forint i=j;i>=n;--i)
13 #define pb push_back
14 using namespace std;
15 inline int getint){
16     int v=0,sign=1; char ch=getchar);
17     whilech<'0'||ch>'9'){ if ch=='-') sign=-1; ch=getchar);}
18     whilech>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar);}
19     return v*sign;
20 }
21 const int N=120000,INF=~0u>>2;
22 typedef long long LL;
23 const double eps=1e-8,pi=acos-1);
24 #define sqrx) x)*x))
25 /******************tamplate*********************/
26   
27 int n;
28 double tx,ty;
29 double a[N],dis[N];
30 typedef pair<double,int> pii;
31 #define mp make_pair
32 pii c[N*6];
33 bool checkdouble d){
34     int s=0,tot=0;
35     Fi,1,n)
36         if dis[i]<=d) s++;
37         else{
38             double l=asind/dis[i]);
39             c[++tot]=mpa[i]-l,1);
40             c[++tot]=mpa[i]+l,-1);
41             if a[i]>0){
42                 c[++tot]=mpa[i]-pi-l,1);
43                 c[++tot]=mpa[i]-pi+l,-1);
44             }else{
45                 c[++tot]=mpa[i]+pi-l,1);
46                 c[++tot]=mpa[i]+pi+l,-1);
47             }
48         }
49     sortc+1,c+tot+1);
50     Fi,1,tot){
51         s+=c[i].second;
52         if s==n) return 1;
53     }
54     return 0;
55 }
56 int main){
57 //  freopen"B.in","r",stdin);
58     n=getint); tx=getint); ty=getint);
59     double l=0,r=0;
60     Fi,1,n){
61         double x=getint),y=getint);
62         a[i]=atan2x-tx,y-ty);
63         dis[i]=sqrtsqrx-tx)+sqry-ty));
64         r=maxdis[i],r);
65     }
66     whiler-l>eps){
67         double mid=l+r)/2;
68         if checkmid)) r=mid;
69         else l=mid;
70     }
71     int ans=floorl*1000);
72     printf"%d.%03d
",ans/1000,ans%1000);
73 //  printf"%.3f
",l-0.0005);
74     return 0;
75 }

View Code

凸凸凸

　　蒟蒻并不会啊……码了个暴力凸包，40分

　　正解好像是这样的……

　　矩形框内离上边界最近的点Up，下边界最近的点Down，左Left，右Right，这四个点一定在最终的凸包上……

　　所以只要预处理出来这四个点之间的凸壳，就可以快速回答询问了QAQ

　　这个好像是满足一个树形的结构？然而蒟蒻并不会写……sad

 1 //XJOI test7 C
 2 #include<vector>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<iostream>
 7 #include<algorithm>
 8 #define repi,n) forint i=0;i<n;++i)
 9 #define Fi,j,n) forint i=j;i<=n;++i)
10 #define Di,j,n) forint i=j;i>=n;--i)
11 #define pb push_back
12 using namespace std;
13 inline int getint){
14     int v=0,sign=1; char ch=getchar);
15     whilech<'0'||ch>'9'){ if ch=='-') sign=-1; ch=getchar);}
16     whilech>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar);}
17     return v*sign;
18 }
19 const int N=6010,INF=~0u>>2;
20 typedef long long LL;
21 /******************tamplate*********************/
22  
23 struct Poi{
24     int x,y;
25     Poi){}
26     Poiint x,int y):xx),yy){}
27     void read){x=getint),y=getint);}
28 }p[N],a[N],st[N],O0,0);
29 typedef Poi Vec;
30 bool operator < const Poi &a,const Poi &b){return a.x<b.x ||a.x==b.x && a.y<b.y);}
31 Vec operator - Poi a,Poi b){return Veca.x-b.x,a.y-b.y);}
32 double Crossconst Poi &a,const Poi &b){return double)a.x*b.y-double)a.y*b.x;}
33  
34 int n,m,top,k;
35  
36 void solve){
37     top=0;
38     Fi,1,m){
39         whiletop>1 && Crossst[top]-st[top-1],a[i]-st[top-1])<=0) top--;
40         st[++top]=a[i];
41     }
42     int k=top;
43     Di,m,1){
44         whiletop>k && Crossst[top]-st[top-1],a[i]-st[top-1])<=0) top--;
45         st[++top]=a[i];
46     }
47     double ans=0.0;
48     Fi,1,top-1) ans+=Crossst[i]-O,st[i+1]-O)/2;
49     printf"%.1f
",ans);
50 }
51  
52 int main){
53     k=getint); n=getint);
54     Fi,1,n) p[i].read);
55     sortp+1,p+n+1);
56     int q=getint);
57     Fi,1,q){
58         m=0;
59         int x1=getint),x2=getint),y1=getint),y2=getint);
60         Fi,1,n) if p[i].x>=x1 && p[i].x<=x2 && p[i].y>=y1 && p[i].y<=y2)
61             a[++m]=p[i];
62         solve);
63     }
64     return 0;
65 }

View Code