# Code Chef IMPO（计算几何+扫描线+积分）

2022年11月23日
0 收藏 945 点赞 4,257 浏览 2786 个字

## 题解

$\int_{l}^rf(x)=\left|{acx^3\over 3}+{(ad+bc)x^2\over 2}+bdx\right|_l^r=F(r)-F(l)$

$F(x)={acx^3\over 3}+{(ad+bc)x^2\over 2}+bdx$

$F(r)-F(l)=(r-l)\left({ac(l^2+lr+r^2)x^3\over 3}+{(ad+bc)(l+r)x^2\over 2}+bdx\right)$

//minamoto#include<bits/stdc++.h>#define R register#define inf 0x3f3f3f3f#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=5e5+5;const double inv3=1.0/3,eps=1e-8;inline int sgn(R double x){return x<-eps?-x:x;}struct Point{int x,y;}A[N],B[N];struct Line{double k,b;inline Line(){}inline Line(R double kk,R double bb):k(kk),b(bb){}inline Line(const Point &p,const Point &q){k=1.0*(q.y-p.y)/(q.x-p.x),b=p.y-p.x*k;}inline Line op(){return Line(-k,-b);}};struct node{Line L;int v;bool k;inline bool operator <(const node &b)const{return v<b.v;}}st[N];int top;void init(int n,Point *a,bool k){a[n+1]=a[1];fp(i,1,n)if(a[i].x!=a[i+1].x){Point p=a[i],q=a[i+1];Line L(p,q);st[++top]={L,p.x,k};st[++top]={L.op(),q.x,k};}}int n,m;int main(){//freopen("testdata.in","r",stdin);for(int T=read();T;--T){int mxa=-inf,mna=inf,mxb=-inf,mnb=inf;top=0;n=read();fp(i,1,n)A[i].x=read(),A[i].y=read(),cmax(mxa,A[i].x),cmin(mna,A[i].x);m=read();fp(i,1,m)B[i].x=read(),B[i].y=read(),cmax(mxb,B[i].x),cmin(mnb,B[i].x);if(mxa!=mxb||mna!=mnb){puts("-1");continue;}init(n,A,0),init(m,B,1);sort(st+1,st+1+top);double l,r,res=0,k[2]={0,0},b[2]={0,0};for(R int i=1;i<top;){l=st[i].v;while(i<=top&&!sgn(st[i].v-l)){k[st[i].k]+=st[i].L.k,b[st[i].k]+=st[i].L.b,++i;}if(i>top)break;r=st[i].v;res+=(r-l)*(k[0]*k[1]*(l*l+l*r+r*r)*inv3+(l+r)*(b[0]*k[1]+b[1]*k[0])*0.5+b[0]*b[1]);}printf("%.10lf\n",res);}return 0;}

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用

400-888-8888

ceotheme@ceo.com