edward_mj

[SGU 217 && HDOJ 3310]微积分

【题目大意】
给两个圆柱体，他们的中轴线共面且垂直。而且这两个圆柱体的高是无限大的。
然后分别给出他们底面的半径r1和r2。
求他们相交的体积。
【算法分析】
按X或Y轴积分怎么搞都搞不过。。。。我倒。。。
按Z轴一积就过了。
还是两个都啰嗦一下吧。
按X或Y轴切得话，切面就是这种形状：“|○|” 然后分类讨论一下那两个竖线夹得地方算面积就可以了。
按Z轴切得话，切面就是”井“字形。然后算矩形面积即可。
【其它】
估计是按X或Y轴切时算面积涉及到arccos和π，所以使误差加大了。。。
【CODE】
#include #include #include #include #define sqr(x) ((x)*(x))
const double pi=acos(-1);
double r1,r2,ans,len,eps,tmp;

inline double f(double x){return sqrt((sqr(r1)-sqr(x))*(sqr(r2)-sqr(x)));}

void work(){
ans=0;
for (double x=0;x+eps ans+=(f(x)+f(x+eps)+f(x+eps/2))/3*eps;
ans*=8;
printf("%.2lfn",ans);
}

int main(){
int Tc;
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%lf%lf",&r1,&r2);
if (r1>r2){tmp=r1; r1=r2; r2=tmp;}
eps=r1/1500000;
work();
}
}

[APIO2010 signaling]计算几何、性质->经典模型

【题目地址】http://www.apio.olympiad.org/
【算法分析】
取4个点，可以推出：
如果是构成凸四边形的话，有两种取法会覆盖完4个点。
如果是构成凹四边形的话，有1种取法会覆盖完4个点。
不要说正方形、矩形。。。题目说明不会有点在外接圆上的。
然后设取4个点中，构成凸四边形的有P个，凹四边形有Q个。
那么P+Q=C(n,4)
然后最终答案ans=(2*P+Q)/C(n,3)+3。
至于求Q。那么就是枚举那个凹四边形中的中心点，然后将其平移至原点，
问题转化成：求N个点中取三个点，过原点的三角形有多少个？
这个是一个经典问题。可以参考这里来解决：
http://hi.baidu.com/edwardmj/blog/item/40751a1454c50414962b4367.html
【CODE】
#include #include #include #include #define next(j) ((j)==n?1:j+1)
using namespace std;
typedef long long lld;
const int N=1505;
struct Point{int x,y;}a[N],tt[N];
int n;
int xx1,xx2;
lld F[N],ans,FM,P,Q;

void input(){
scanf("%d",&n);
int i;
for (i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
}

inline int get_xx(Point p){
if (p.x>=0 && p.y>0) return 1;
if (p.x>0 && p.y<=0) return 2;
if (p.x<=0 && p.y<0) return 3;
return 4;
}

inline int cj(Point &p0,Point &p1,Point &p2){
lld res=(lld)(p1.x-p0.x)*(lld)(p2.y-p0.y)-(lld)(p1.y-p0.y)*(lld)(p2.x-p0.x);
if (res<0) return -1;
if (res==0) return 0;
return 1;
}

inline bool cmp(Point x,Point y){
xx1=get_xx(x),xx2=get_xx(y);
if (xx1!=xx2) return xx1 return cj(a[0],x,y)<0;
}

void solve(){
sort(a+1,a+1+n,cmp);
ans+=(lld)(n)*(n-1)*(n-2)/6;
lld total;
int i,j=1;
for (i=1;i<=n;i++){
if (i==j) j=next(j);
while (i!=next(j) && cj(a[0],a[i],a[next(j)])<0) j=next(j);
if (j else total=j-i;
ans-=total*(total-1)/2;
}
}

inline void swap(Point &X,Point &Y){Point tmp=X; X=Y; Y=tmp;}

void work(){
FM=(lld)(n)*(n-1)*(n-2)/6;
ans=0;
memcpy(tt,a,sizeof(tt));
int i,j;
n;
for (i=1;i<=n;i++){
for (j=1;j<=n;j++) a[j]=tt[j];
swap(a[n],a[i]);
for (j=1;j a[j].x-=a[n].x;
a[j].y-=a[n].y;
}
n–;
solve();
n++;
}
Q=ans;
P=(lld)(n)*(n-1)*(n-2)*(n-3)/24-Q;
ans=2*P+Q;
printf("%.3lfn",(double)ans/(double)(FM)+3);
}

int main(){
freopen("signaling.in","r",stdin);
freopen("signaling.out","w",stdout);
input();
work();
}

[APIO2010 patrol]树形动态规划

【题目地址】http://www.apio.olympiad.org/
【算法分析】
就是求两（一）条不相交的最长链。
F[i][j][k]表示i这个结点，已完成的链有j条，k表示有无一条只有一边的可延伸链，所得到的最大长度。
然后就像背包一样转移。
【CODE】
#include #include #include const int N=100005;
struct edge{int x,y;edge *next;}sp[N*2],*ls[N];
int n,L,e,tot;
int F[N][3][2],pF[3][2];

inline void addedge(int x,int y){
sp[++e].x=x; sp[e].y=y; sp[e].next=ls[x]; ls[x]=&sp[e];
}

void init(){
e=0;
memset(ls,0,sizeof(ls));
int i,x,y;
scanf("%d%d",&n,&L);
for (i=1;i scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
}

inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x for (edge *t=ls[p];t;t=t->next)
if (t->y!=fa) dp(t->y,t->x);
F[p][0][0]=0;
F[p][0][1]=0;
int j,k,pj,pk;
tot=0;
for (edge *t=ls[p];t;t=t->next) if (t->y!=fa){
memcpy(pF,F[p],sizeof(pF));
for (j=0;j<=L;j++)
for (pj=0;pj+j<=L;pj++){
F[p][pj+j][0]=max(F[p][pj+j][0],pF[pj][0]+F[t->y][j][0]);
F[p][pj+j][1]=max(F[p][pj+j][1],pF[pj][0]+F[t->y][j][1]+1);
F[p][pj+j][1]=max(F[p][pj+j][1],pF[pj][1]+F[t->y][j][0]);
if (pj+j+1<=L)
F[p][pj+j+1][0]=max(F[p][pj+j+1][0],pF[pj][1]+F[t->y][j][1]+1);
}
}
}

void solve(){
int ans=0;
memset(F,200,sizeof(F));
dp(1,0);
ans=max(ans,F[1][1][0]);
ans=max(ans,F[1][0][1]);
if (L==2){
ans=max(ans,F[1][1][1]);
ans=max(ans,F[1][2][0]);
}
printf("%dn",2*n-2-ans+L);
}

int main(){
freopen("patrol.in","r",stdin);
freopen("patrol.out","w",stdout);
init();
solve();
return 0;
}

[APIO2010 commando]斜率优化1D/1D方程、动态规划

【题目地址】http://www.apio.olympiad.org/
【算法分析】
易得方程F[i]=F[j]+g(Si-Sj) g为那个二次函数。
然后列不等式F[j]+g(Si-Sj)变形得(F[j]-F[k]+a*(Sum[j]*Sum[j]-Sum[k]*Sum[k])+b*(Sum[k]-Sum[j])) / ((Sum[j]-Sum[k])*a*2) <=Si。
然后这就是经典的斜率优化dp。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
const int N=1000005;
const lld INF=(lld)(1)<<60;
int n,a,b,c;
int xl[N],Q[N];
lld Sum[N],F[N];
char ch;
bool fu;

void Read(int &x){
ch=getchar();
while (!(ch>=’0′ && ch<='9' || ch=='-')) ch=getchar();
x=0;
fu=false;
if (ch==’-‘){
fu=true;
ch=getchar();
}
while (ch>=’0′ && ch<='9'){
x=x*10+ch-‘0’;
ch=getchar();
}
if (fu) x=-x;
}

void input(){
Read(n);
Read(a); Read(b); Read(c);
for (int i=1;i<=n;i++)
Read(xl[i]);
Sum[0]=0;
for (int i=1;i<=n;i++)
Sum[i]=Sum[i-1]+xl[i];
}

inline lld g(lld x){return x*x*a+x*b+c;}
inline lld pos(int j,int k){
return (F[j]-F[k]+a*(Sum[j]*Sum[j]-Sum[k]*Sum[k])+b*(Sum[k]-Sum[j]))/
((Sum[j]-Sum[k])*a);
}

void work(){
int i,j,h,t;
h=t=1; Q[1]=0;
F[0]=0;
for (i=1;i<=n;i++) F[i]=-INF;
for (i=1;i<=n;i++){
while (h F[i]=F[Q[h]]+g(Sum[i]-Sum[Q[h]]);
while (h t++;
Q[t]=i;
}
cout << F[n] << endl;
}

int main(){
freopen("commando.in","r",stdin);
freopen("commando.out","w",stdout);
input();
work();
}

[Elite 2010 U S Open Competition]求过原点的三角形数目、极角排序、维护

【题目大意】
给定N个二维平面上的点。
问他们取3个出来，过原点的三角形有多少个。
【算法分析】
先极角排序。
然后维护一个最长区间，使得区间中任意一个点对满足向量(O, i)和向量(O, j)的夹角【其它】
APIO最后一题的本质模型。
【CODE】
/*
ID:jie22221
TASK:tricount
LANG:C++
*/

#include #include #include #include using namespace std;
typedef long long lld;
const int N=100005;
int n;
struct Point{int x,y;}a[N];

void input(){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
}

int get_xx(Point p){
if (p.x>=0 && p.y>0) return 1;
if (p.x>0 && p.y<=0) return 2;
if (p.x<=0 && p.y<0) return 3;
return 4;
}

int cj(Point p0,Point p1,Point p2){
lld res=(lld)(p1.x-p0.x)*(lld)(p2.y-p0.y)-(lld)(p1.y-p0.y)*(lld)(p2.x-p0.x);
if (res<0) return -1;
if (res==0) return 0;
return 1;
}

int cmp(const void *X,const void *Y){
Point x=*((Point*)X),y=*((Point*)Y);
int xx1=get_xx(x),xx2=get_xx(y);
if (xx1!=xx2) return xx1-xx2;
return cj(a[0],x,y);
}

void solve(){
lld ans=(lld)(n)*(n-1)*(n-2)/6,total;
int i,j=1;
for (i=1;i<=n;i++){
if (i==j) j=j%n+1;
while (i!=j%n+1 && cj(a[0],a[i],a[j%n+1])<0) j=j%n+1;
if (j else total=j-i;
ans-=total*(total-1)/2;
}
cout << ans << endl;
}

int main(){
freopen("tricount.in","r",stdin);
freopen("tricount.out","w",stdout);
input();
qsort(a+1,n,sizeof(Point),cmp);
solve();
}