HDU 5462 2015沈阳网络赛 Manors （半平面交）

网友投稿 292 2022-08-27

HDU 5462 2015沈阳网络赛 Manors （半平面交）

​​ 题解：先根据I(i)==I(j)列方程整理方程。 Ii=Ij

所以 ∑mk=1((x−xi)2+(y−yi)2)=∑mk=1((x−xj)2+(y−yj)2)

所以 ∑mk=1(x2−2xxi+x2i+y2−2yyi+y2i)=∑mk=1(x2−2xxj+x2j+y2−2yyj+y2j)

所以 −2∑mk=1(xi−xj)∗x−2∑mk=1(yi−yj)∗y+∑mk=1(x2i−x2j+y2i−y2j)=0

可令： A=−2∑mk=1(xi−xj)

B=−2∑mk=1(yi−yj)

C=∑mk=1(x2i−x2j+y2i−y2j)

发现整理之后恰好是一条直线Ax + By + C = 0。 因为系数是前缀和或者是平方和，先预处理，然后扫一遍这n个人，每个人对应n-1个直线，同时加上4个边界直线，一共n-1+4=n+3条直线，求半平面交后再求面积，就是第i个人的面积。时间复杂度O(N^3logN)。

#pragma comment(linker, "/STACK:102400000,102400000")//#include#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair pii;typedef vector vi;const double eps = 1e-8; const int INF = 1e9+7; const ll inf =(1LL<<62) ;const int MOD = 1e9 + 7; const ll mod = (1LL<<32);const int N =110; const int M=100010;const int maxn=1001;#define mst(a) memset(a, 0, sizeof(a))#define M_P(x,y) make_pair(x,y)#define pi acos(-1.0)#define in freopen("in.txt","r",stdin) #define rep(i,j,k) for (int i = j; i <= k; i++) #define per(i,j,k) for (int i = j; i >= k; i--) #define lson x << 1, l, mid #define rson x << 1 | 1, mid + 1, r const int lowbit(int x) { return x&-x; }//const int lowbit(int x) { return ((x)&((x)^((x)-1))); } int read(){ int v = 0, f = 1;char c =getchar();while( c < 48 || 57 < c ){if(c=='-') f = -1;c = getchar();}while(48 <= c && c <= 57) v = v*10+c-48, c = getchar();return v*f;}struct Point{ double x,y; Point(double x=0,double y=0):x(x),y(y){}};typedef Point Vector;Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}Vector operator*(Vector a,double p){return Vector(a.x*p,a.y*p);}double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}double Length(Vector a){return sqrt(Dot(a,a));}Vector Normal(Vector a){double L=Length(a);return Vector(-a.y/L,a.x/L);}double PolygonArea(vectorp){ int n=p.size(); double area=0; for(int i=1;i0;}Point GetLineIntersection(Line a,Line b){ Vector u=a.p-b.p; double t=Cross(b.v,u)/Cross(a.v,b.v); return a.p+a.v*t;}vector HalfplaneIntersection(vectorL){ int n=L.size(); sort(L.begin(),L.end()); int first,last; vector p(n); vector q(n); vector ans; q[first=last=0]=L[0]; for(int i=1;ip,poly;Point person[N][2020];Point sum[N];Point sum2[N];double ans[N];int main(){ int T; int rnd=0; scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); for(int i=0;iL; for(int j=0;jfabs(b))p=Point(-c/a,0); else p=Point(0,-c/b); Vector v(b,-a); L.push_back(Line(p,v)); } L.push_back(Line(Point(0,0),Vector(0,-1))); L.push_back(Line(Point(4095,0),Vector(0,1))); L.push_back(Line(Point(0,0),Vector(1,0))); L.push_back(Line(Point(4095,4095),Vector(-1,0))); vectorch=HalfplaneIntersection(L); ans[i]=fabs(PolygonArea(ch)); } printf("Case #%d:",++rnd); for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：网络
上一篇:AIM Tech Round 3 (Div. 2) E. Centroids （树形dp）
下一篇:2022年户外营销预算上涨25%，线下媒体或将迎来新增量！（2020户外广告发展分析）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~