【学习】计算几何

Jacinth posted @ 2016年10月17日 22:07 in Lerning with tags 学习计算几何 Learning bzoj , 820 阅读

感觉数学课要好好听噫

真的只有几道题，其他什么都没有哒

BZOJ-2338: [HNOI2011]数矩形

把所有点的连线按照中点和长度排序，只有中点和长度相等的才能构成长方形。

然后就好办辣。

BZOJ-2338
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67	`#include <bits/stdc++.h>` `using` `namespace` `std;` `typedef` `long` `long` `LL;` `const` `int` `NN = 1600;` `int` `n,cnt=0;` `LL ans;` `struct` `Pts` `{` `LL x,y;` `Pts() {}` `Pts(LL _,LL __):x(_),y(__){}` `bool` `operator == (const` `Pts &xx)` `const` `{` `return` `x == xx.x && y == xx.y;` `}` `Pts operator - (const` `Pts &xx)` `const` `{` `return` `Pts(x-xx.x,y-xx.y);` `}` `LL operator * (const` `Pts &xx)` `const` `{` `return` `xxx.y-xx.xy;` `}` `}points[NN];` `struct` `L` `{` `LL len;` `Pts p1,p2;` `Pts mid;` `}lines[NNNN>>1];` `bool` `cmp(L xx,L yy)` `{` `if` `(xx.len == yy.len)` `{` `if` `(xx.mid.x == yy.mid.x)` `return` `xx.mid.y<yy.mid.y;` `return` `xx.mid.y < yy.mid.y;` `}` `return` `xx.len < yy.len;` `}` `LL A_LL(LL xx) {` `return` `xx<0ll?-xx:xx; }` `LL sqr(LL xx) {` `return` `xxxx; }` `LL Dis(const` `Pts &p1,const` `Pts &p2)` `{` `return` `sqr(p1.x-p2.x)+sqr(p1.y-p2.y);` `}` `int` `main()` `{` `scanf("%d",&n);` `for` `(int` `i=1;i<=n;++i)` `{` `scanf("%lld%lld",&points[i].x,&points[i].y);` `for` `(int` `j=1;j<i;++j)` `{` `lines[++cnt].len = Dis(points[i],points[j]);` `lines[cnt].p1 = &points[i], lines[cnt].p2 = &points[j];` `lines[cnt].mid = Pts(points[i].x+points[j].x,points[i].y+points[j].y);` `}` `}` `sort(lines+1,lines+1+cnt,cmp);` `for` `(int` `i=1;i<=cnt;++i)` `{` `for` `(int` `j=i-1;j && lines[i].len == lines[j].len && lines[i].mid == lines[j].mid;--j)` `ans = max(ans, A_LL(((lines[i].p1)-(lines[j].p1))((lines[i].p1)-(*lines[j].p2))));` `}` `printf("%lld\n",ans);` `return` `0;` `}`

BZOJ-1043: [HAOI2008]下落的圆盘

直接考虑每个圆在后面的圆砸完以后还剩下多少就可以了

相关只是都是数学书必修&选修&老师课上的内容啦

BZOJ-1043
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67	`#include <iostream>` `#include <cstdio>` `#include <cmath>` `#include <cstring>` `#include <algorithm>` `#include <cstdlib>` `#define pi acos(-1)` `using` `namespace` `std;` `const` `int` `NN = 1005;` `int` `n,top;` `double` `ans,x[NN],y[NN],r[NN];` `struct` `Line` `{` `double` `l,r;` `}a[NN];` `bool` `cmp(Line xx,Line yy) {` `return` `xx.l<yy.l; }` `inline` `double` `sqr(double` `xx) {` `return` `xxxx; }` `inline` `double` `Dis(int` `xx,int` `yy) {` `return` `sqrt(sqr(x[xx]-x[yy])+sqr(y[xx]-y[yy])); }` `bool` `Check(int` `xx,int` `yy)` `{` `if` `(r[xx] >= r[yy] + Dis(xx,yy))` `return` `1;` `else` `return` `0;` `}` `void` `Ins(int` `xx,int` `yy)` `{` `double` `d,tmp,st,l;` `d = Dis(xx,yy);` `tmp = (sqr(r[xx])-sqr(r[yy])+sqr(d))/(2.0d);` `st =` `atan2((x[xx]-x[yy]),(y[xx]-y[yy]));` `l =` `acos(tmp/r[xx]);` `a[++top].l = st-l, a[top].r = st+l;` `}` `double` `Cal(int` `xx)` `{` `for` `(int` `i=xx+1;i<=n;++i)` `if` `(Check(i,xx))` `return` `0;` `top = 0;` `for` `(int` `i=xx+1;i<=n;++i)` `if` `(!Check(xx,i) && r[xx]+r[i] >= Dis(xx,i)) Ins(xx,i);` `double` `tmp = 0, now = 0;` `for` `(int` `i=1;i<=top;++i)` `{` `if` `(a[i].l < 0) a[i].l += 2.0pi;` `if` `(a[i].r < 0) a[i].r += 2.0pi;` `if` `(a[i].l > a[i].r)` `{` `a[++top].l = 0, a[top].r = a[i].r, a[i].r = 2.0pi;` `}` `}` `sort(a+1,a+top+1,cmp);` `for` `(int` `i=1;i<=top;++i)` `if` `(a[i].l > now) tmp += a[i].l - now, now = a[i].r;` `else` `now = max(now,a[i].r);` `tmp += 2.0pi-now;` `return` `tmp * r[xx];` `}` `int` `main()` `{` `scanf("%d",&n);` `for` `(int` `i=1;i<=n;++i)` `scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);` `for` `(int` `i=1;i<=n;++i) ans += Cal(i);` `printf("%.3lf\n",ans);` `return` `0;` `}`

BZOJ-1074: [SCOI2007]折纸origami

找到可能的点，然后一一判断折回来符不符合就可以了

BZOJ-1074
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85	`#include <bits/stdc++.h>` `using` `namespace` `std;` `const` `double` `eps = 1e-6;` `const` `int` `INF = 1<<29;` `struct` `Point` `{` `double` `x,y;` `inline` `friend` `bool` `operator == (Point xx,Point yy)` `{` `return` `fabs(xx.x-yy.x)<eps &&` `fabs(xx.y-yy.y)<eps;` `}` `};` `const` `Point Wr=(Point){-INF,-INF},Sg=(Point){INF,INF};` `struct` `Line` `{` `Point st,en;` `};` `int` `n,m,ans;` `Line a[10001];` `inline` `double` `Cross(Point a,Point b)` `{` `return` `a.xb.y - a.yb.x;` `}` `Point Rotate(Point xx,Line yy)` `{` `Point tx,ty;` `tx.x = xx.x-yy.st.x;` `tx.y = xx.y-yy.st.y;` `ty.x = yy.en.x-yy.st.x;` `ty.y = yy.en.y-yy.st.y;` `Point res;` `if` `(Cross(ty,tx) > eps)` `{` `if` `(fabs(yy.st.x-yy.en.x) < eps) res.x = 2yy.st.x-xx.x, res.y = xx.y;` `else` `if` `(fabs(yy.st.y-yy.en.y) < eps) res.x = xx.x, res.y = 2yy.st.y-xx.y;` `else` `{` `double` `k=yy.en.y - yy.st.y, k1;` `k /= yy.en.x - yy.st.x;` `k1 = -1/k;` `double` `b = yy.en.xyy.st.y-yy.en.yyy.st.x, b1;` `b /= yy.en.x - yy.st.x;` `if` `(fabs(xx.x) < eps) b1 = xx.y;` `else` `b1 = xx.y-k1xx.x;` `res.x = (b1-b)/(k-k1), res.y = kres.x+b;` `res.x = 2, res.y = 2;` `res.x -= xx.x, res.y -= xx.y;` `}` `return` `res;` `}` `if` `(Cross(ty,tx) < -eps)` `return` `Wr;` `return` `Wr;` `}` `bool` `Check(Point xx)` `{` `return` `xx.x>eps && xx.x<100-eps && xx.y>eps && xx.y<100-eps;` `}` `void` `DFS(Point xx,int` `t)` `{` `if` `(t == 0) {` `if` `(Check(xx)) ++ ans;` `return;}` `Point yy = Rotate(xx,a[t]);` `if` `(yy == Wr)` `return;` `else` `if` `(yy == Sg) DFS(xx,t-1);` `else` `DFS(yy,t-1), DFS(xx,t-1);` `}` `int` `main()` `{` `scanf("%d",&n);` `for` `(int` `i=1;i<=n;++i)` `scanf("%lf%lf%lf%lf",&a[i].st.x,&a[i].st.y,&a[i].en.x,&a[i].en.y);` `scanf("%d",&m);` `for` `(int` `i=1;i<=m;++i)` `{` `Point tp;` `ans = 0;` `scanf("%lf%lf",&tp.x,&tp.y);` `DFS(tp,n);` `printf("%d\n",ans);` `}` `return` `0;` `}`

BZOJ-2458: [BeiJing2011]最小三角形

分治。每次分成左右两部分，然后对于中间的用双指针保证距离不大于 $\frac{1}{2}ans$ ，然后统计就可以了。

BZOJ-2458
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47	`#include <bits/stdc++.h>` `using` `namespace` `std;` `const` `int` `NN = 200200;` `const` `double` `INF = 1e50;` `struct` `P` `{` `int` `x,y;` `}a[NN],num[NN];` `int` `n;` `bool` `cmp(P xx,P yy) {` `if` `(xx.x == yy.x)` `return` `xx.y<yy.y;` `else` `return` `xx.x<yy.x; }` `bool` `cmpp(P xx,P yy) {` `if` `(xx.y == yy.y)` `return` `xx.x<yy.x;` `else` `return` `xx.y<yy.y; }` `double` `sqr(int` `xx) {return` `1.0xxxx; }` `double` `Dis(P xx,P yy) {` `return` `sqrt(sqr(xx.x-yy.x)+sqr(xx.y-yy.y));}` `inline` `double` `Solve(int` `l,int` `r)` `{` `if` `(l == r)` `return` `INF;` `if` `(l+1 == r)` `return` `INF;` `if` `(l+2 == r)` `return` `Dis(a[l],a[l+1]) + Dis(a[l+1],a[r]) + Dis(a[l],a[r]);` `int` `mid = (l+r) >> 1;` `double` `D = min(Solve(l,mid),Solve(mid+1,r)), ans = D, DD = D/2.0;` `int` `cnt = 0;` `for` `(int` `i=l;i<=r;++i)` `if` `(fabs(a[mid].x-a[i].x) <= DD) num[++cnt] = a[i];` `sort(num+1,num+cnt+1,cmpp);` `for` `(int` `i=1;i<cnt-1;++i)` `for` `(int` `j=i+1;j<cnt;++j)` `{` `if` `(num[j].y - num[i].y > DD)` `break;` `for` `(int` `k=j+1;k<=cnt;++k)` `{` `if` `(num[k].y - num[i].y > DD)` `break;` `double` `tmp = Dis(num[i],num[j]) + Dis(num[i],num[k]) + Dis(num[j],num[k]);` `ans = min(ans,tmp);` `}` `}` `return` `ans;` `}` `int` `main()` `{` `scanf("%d",&n);` `for` `(int` `i=1;i<=n;++i)` `scanf("%d%d",&a[i].x,&a[i].y);` `sort(a+1,a+1+n,cmp);` `printf("%.6lf",Solve(1,n));` `return` `0;` `}`

[回复]

Meghalaya Board Ques 说:
2022年8月25日 19:32

Meghalaya Board Model Paper 2023 Class 10 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Meghalaya Board Question Paper Class 10 Type Questions to Term1 & Term2 Exams at official website. New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.

Pluto_Rabbit's Blog

蒟蒻妹纸一枚，轻拍

【学习】计算几何

BZOJ-2338: [HNOI2011]数矩形

BZOJ-1043: [HAOI2008]下落的圆盘

BZOJ-1074: [SCOI2007]折纸origami

BZOJ-2458: [BeiJing2011]最小三角形

lujiaxin

搜索

乱七八糟的分类

友链墙

计数君

标签君

Flag君