博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
qwq
阅读量:4599 次
发布时间:2019-06-09

本文共 12488 字,大约阅读时间需要 41 分钟。

#include
#define IL inline#define _ 100005#define ll long longusing namespace std ;IL int gi(){ int data = 0 , m = 1; char ch = 0; while(ch!='-' && (ch<'0'||ch>'9')) ch = getchar(); if(ch == '-'){m = 0 ; ch = getchar() ; } while(ch >= '0' && ch <= '9'){data = (data<<1) + (data<<3) + (ch^48) ; ch = getchar(); } return (m) ? data : -data ; }#define ld long double#define inf 1e9#define eps 1e-6int n ; const ld PI = acos(-1.0) ;struct Point{ ld x , y ; IL Point(){x = 0 ; y = 0 ; } IL Point(double a , double b){x = a ; y = b ; } IL ld cal() {return sqrt(x*x + y*y) ; } IL void Print(){printf("(%Lf,%Lf)" , x , y) ; }} ;IL Point operator + (Point a , Point b) {return Point(a.x + b.x , a.y + b.y) ; }IL Point operator - (Point a , Point b) {return Point(a.x - b.x , a.y - b.y) ; }IL ld operator ^ (Point a , Point b) {return a.x * b.x + a.y * b.y ; }IL ld operator * (Point a , Point b) {return a.x * b.y - a.y * b.x ; }IL Point operator * (Point a , double b) {return Point(a.x * b , a.y * b) ; }IL ld Sqr(ld x) {return 1.0 * x * x ; }IL ld Dist(Point a , Point b) {return sqrt(Sqr(a.x - b.x) + Sqr(a.y - b.y)) ; }IL Point Rot(Point a , ld Arc) { return Point(cos(Arc)*a.x - sin(Arc)*a.y , sin(Arc)*a.x + cos(Arc)*a.y) ; }struct Line { Point p1 , p2 ; IL Line() {p1 = Point() ; p2 = Point() ; } IL Line(Point a , Point b) {p1 = a ; p2 = b ; } IL void Print(){p1.Print() ; putchar('-') ; putchar('-') ; putchar('>') ; p2.Print() ; }} ;IL Line Perp(Line A) { Point a = A.p1 , b = A.p2 , c ; c = b - a ; c = Rot(c , PI * 0.5) ; return Line((a + b) * 0.5 , ((a + b) * 0.5) + c * 0.5) ; }IL Point GetCross(Line l1 , Line l2) { Point a = l1.p2 - l1.p1 , b = l2.p2 - l2.p1 , c = l2.p1 - l1.p1 ; ld al = (a * c) / (b * a) ; return Point(l2.p1.x + b.x * al , l2.p1.y + b.y * al) ;}IL ld Dist(Line l1 , Point ps) { Point w = l1.p2 - l1.p1 ; return fabs(w * (ps - l1.p1)) / Dist(l1.p1 , l1.p2) ;}Point p[_] , circle_p ;ld circle_range ; namespace CirCle{ IL void Print_Circle() { printf("%.8Lf %.8Lf %.8Lf\n" , circle_p.x , circle_p.y , circle_range) ; return ; } IL void main() { random_shuffle(p + 1 , p + n + 1) ; random_shuffle(p + 1 , p + n + 1) ; circle_p = p[1] ; circle_range = 0 ; for(int i = 2; i <= n; i ++) if(Dist(circle_p , p[i]) > circle_range) { circle_p = p[i] ; circle_range = 0 ; for(int j = 1; j < i; j ++) if(Dist(circle_p , p[j]) > circle_range) { circle_p = (p[i] + p[j]) * 0.5 ; circle_range = Dist(circle_p , p[i]) ; for(int k = 1; k < j; k ++) if(Dist(circle_p , p[k]) > circle_range) { Line l1 , l2 ; l1 = Line(p[k] , p[j]) ; l2 = Line(p[i] , p[j]) ; l1 = Perp(l1) ; l2 = Perp(l2) ; circle_p = GetCross(l1 , l2) ; circle_range = Dist(circle_p , p[i]) ; } } } Print_Circle() ; }}Point Base_p , gm[_] ; int nG , tot ;namespace GraHam{ IL bool cmp_GraHam(Point a , Point b) { return (a - Base_p) * (b - Base_p) > 0 ; } IL void Print_GraHam() { for(int i = 0; i <= nG; i ++) { gm[i].Print() ; putchar('-') ; putchar('-') ; putchar('>') ; } puts("") ; return ; } IL void main() { nG = 0 ; Base_p = p[1] ; int id = 1 ; for(int i = 2; i <= n; i ++) if(p[i].x < Base_p.x || (fabs(p[i].x-Base_p.x)<=eps && p[i].y < Base_p.y)) Base_p = p[i] , id = i ; tot = 0 ; for(int i = 1; i <= n; i ++) if(id != i) p[++tot] = p[i] ; n = tot ; sort(p + 1 , p + n + 1 , cmp_GraHam) ; gm[nG = 0] = Base_p ; gm[++ nG] = p[1] ; for(int i = 2; i <= n; i ++) { while(nG >= 1 && (p[i] - gm[nG - 1]) * (gm[nG] - gm[nG -1]) > 0) -- nG ; gm[++nG] = p[i] ; } //Print_GraHam() ; return ; }}Point tmp_matrix[10] , matrix_p[10] ;namespace Matrix{ IL bool cmp_Sort_Matrix(Point a , Point b) { return (a - matrix_p[0]) * (b - matrix_p[0]) >= 0 ; } IL void Print_Matrix() { Point w = tmp_matrix[1] - tmp_matrix[0] , delta ; double l , l1 , l2 , l3 ; l = Dist(tmp_matrix[0] , tmp_matrix[1]) ; l2 = (w ^ (tmp_matrix[2] - tmp_matrix[0])) / l ; delta = w * (l2 / l) ; matrix_p[1] = tmp_matrix[0] + delta ; l1 = (w ^ (tmp_matrix[4] - tmp_matrix[0])) / l ; delta = w * (l1 / l) ; matrix_p[0] = tmp_matrix[0] + delta ; Point up = w ; up = Rot(w , PI * 0.5) ; l3 = up.cal() ; l = Dist(Line(tmp_matrix[0] , tmp_matrix[1]) , tmp_matrix[3]) ; up = up * (l / l3) ; matrix_p[2] = matrix_p[1] + up ; matrix_p[3] = matrix_p[0] + up ; int id = 0 ; for(int i = 1; i <= 3; i ++) if(matrix_p[i].x < matrix_p[id].x) id = i ; else if(fabs(matrix_p[i].x - matrix_p[id].x) <= eps && matrix_p[i].y < matrix_p[id].y) id = i ; swap(matrix_p[id] , matrix_p[0]) ; sort(matrix_p + 1 , matrix_p + 3 + 1 , cmp_Sort_Matrix) ; for(int i = 0; i <= 3; i ++) printf("%.8Lf %.8Lf " , matrix_p[i].x , matrix_p[i].y) ; puts("") ; return ; } IL void main() { ld now_C = 1e9 ; ++ nG ; for(int i = 0,lft,rg = 1,up = 2; i < nG; i ++) { Point w = gm[(i+1)%nG] - gm[i] ; while(w * (gm[up] - gm[i]) <= w * (gm[(up+1)%nG] - gm[i])) up = (up + 1) % nG ; if(i == 0) lft = up ; while((w ^ (gm[rg] - gm[i])) - eps <= (w ^ (gm[(rg+1)%nG] - gm[i]))) rg = (rg + 1) % nG ; while((w ^ (gm[lft] - gm[i])) + eps >= (w ^ (gm[(lft+1)%nG] - gm[i]))) lft = (lft + 1) % nG ; ld al = 0.0 , bh ; bh = Dist(Line(gm[i] , gm[(i+1)%nG]) , gm[up]) ; al += fabs((w ^ (gm[rg] - gm[i]))) ; al += fabs((w ^ (gm[lft] - gm[i]))) ; al /= Dist(gm[i] , gm[(i+1) % nG]) ; if(2.0 * (al + bh) < now_C) { tmp_matrix[0] = gm[i] , tmp_matrix[1] = gm[(i+1)%nG] , tmp_matrix[2] = gm[lft] ; tmp_matrix[3] = gm[up] , tmp_matrix[4] = gm[rg] ; now_C = 2.0 * (al + bh) ; } } -- nG ; Print_Matrix() ; return ; }}Point tmp_triange[10] , triange_p[10] ;namespace Triange{ IL ld Calc_right(Point a , Point w , Point c , double lw) { ld d = (w ^ (c - a)) / lw , h = Dist(Line(a , a + w) , c) ; return h / sqrt(3.0) + d ; } IL ld Calc_left(Point a , Point w , Point c , double lw) { ld d = (w ^ (c - a)) / lw , h = Dist(Line(a , a + w) , c) ; return - h / sqrt(3.0) + d ; } IL bool cmp_Sort_Triange(Point a , Point b) { return (a - triange_p[0]) * (b - triange_p[0]) >= 0 ; } IL void Print_Triange() { ld l1 , l2 , l = Dist(tmp_triange[0] , tmp_triange[1]) , lg ; Point w = tmp_triange[1] - tmp_triange[0] , delta ; l1 = Calc_right(tmp_triange[0] , w , tmp_triange[2] , l) ; triange_p[1] = tmp_triange[0] + w * (l1 / l) ; l2 = Calc_left(tmp_triange[0] , w , tmp_triange[3] , l) ; triange_p[0] = tmp_triange[0] + w * (l2 / l) ; lg = fabs(l1) + fabs(l2) ; Line al0 , al1 ; delta = Rot(w , PI / 3.0) ; al0 = Line(triange_p[0] , triange_p[0] + delta * (lg / l)) ; delta = Rot(delta , PI / 3.0) ; al1 = Line(triange_p[1] , triange_p[1] + delta * (lg / l)) ; triange_p[2] = GetCross(al0 , al1) ; int id = 0 ; for(int i = 1; i <= 2; i ++) if(triange_p[i].x < triange_p[id].x) id = i ; else if(fabs(triange_p[i].x - triange_p[id].x) <= eps && triange_p[i].y < triange_p[id].y) id = i ; swap(triange_p[id] , triange_p[0]) ; sort(triange_p + 1 , triange_p + 2 + 1 , cmp_Sort_Triange) ; for(int i = 0; i <= 2; i ++) printf("%.8Lf %.8Lf " , triange_p[i].x , triange_p[i].y) ; puts("") ; return ; } IL void main() { ld now_C = 1e9 , al ; ++ nG ; for(int i = 0,lft = 1 , rgt = 1,up = 1; i < nG; i ++) { Point w = gm[(i+1)%nG] - gm[i] ; ld lw = Dist(gm[(i+1)%nG] , gm[i]) ; while(w * (gm[up] - gm[i]) <= w * (gm[(up+1)%nG] - gm[i])) up = (up + 1) % nG ; if(i == 0) lft = up ; while(Calc_right(gm[i] , w , gm[rgt] , lw) - eps <= Calc_right(gm[i] , w , gm[(rgt+1)%nG] , lw)) rgt = (rgt + 1) % nG ; while(Calc_left(gm[i] , w , gm[lft] , lw) + eps >= Calc_left(gm[i] , w , gm[(lft+1)%nG] , lw)) lft = (lft + 1) % nG ; al = 0.0 ; al += fabs(Calc_left(gm[i] , w , gm[lft] , lw)) ; al += fabs(Calc_right(gm[i] , w , gm[rgt] , lw)) ; if(3.0 * al <= now_C) { tmp_triange[0] = gm[i] ; tmp_triange[1] = gm[(i+1) % nG] ; tmp_triange[2] = gm[rgt] ; tmp_triange[3] = gm[lft] ; now_C = 3.0 * al ; } } -- nG ; Print_Triange() ; return ; }}Point gc[_] , tmp_gc[_] ; int nC ; namespace Divide_Cut{ IL void Print_Divide_Cut() { for(int i = 1; i <= nC; i ++) { gc[i].Print() ; putchar('-') ; putchar('-') ; putchar('>') ; } puts("") ; return ; } IL void Cut(Point a , Point b) { gc[nC + 1] = gc[1] ; tot = 0; Point w = b - a ; for(int i = 1; i <= nC; i ++) { ld test1 = (a - gc[i]) * (b - gc[i]) ; if(test1 >= 0.0) tmp_gc[++tot] = gc[i] ; ld test2 = (a - gc[i+1]) * (b - gc[i+1]) ; if(test2 * test1 < 0) tmp_gc[++tot] = GetCross(Line(a , b) , Line(gc[i] , gc[i + 1])) ; } for(int i = 1; i <= tot; i ++) gc[i] = tmp_gc[i] ; nC = tot ; } IL void main() { gc[++nC] = Point(-inf,-inf) ; gc[++nC] = Point(inf,-inf) ; gc[++nC] = Point(inf,inf) ; gc[++nC] = Point(-inf,inf) ; for(int i = 0; i <= 3; i ++) { Cut(matrix_p[i] , matrix_p[(i+1)%4]) ; } for(int i = 0; i <= 2; i ++) Cut(triange_p[i] , triange_p[(i+1)%3]) ; //Print_Divide_Cut() ; return ; }}ld circle_pl , circle_pr , polygon_pl , polygon_pr , Ans ;namespace Simpson_Int{ IL ld F(ld x) { if(!(circle_p.x - circle_range - eps <= x && x <= circle_p.x + circle_range + eps)) return 0 ; ld d = sqrt(Sqr(circle_range) - Sqr(fabs(x - circle_p.x))) ; circle_pl = circle_p.y - d ; circle_pr = circle_p.y + d ; polygon_pl = inf ; polygon_pr = -inf ; tot = 0 ; for(int i = 1; i <= nC; i ++) if((gc[i].x - eps <= x && gc[i%nC + 1].x + eps >= x) || (gc[i%nC + 1].x - eps <= x && gc[i].x + eps >= x) ) { Point al = GetCross(Line(gc[i] , gc[i%nC+1]) , Line(Point(x,0) , Point(x,1))) ; polygon_pl = min(polygon_pl , al.y) ; polygon_pr = max(polygon_pr , al.y) ; } //cout << "circle: ["<
<<","<
<<"]" << endl ; //cout << "polygon: ["<< polygon_pl<<","<
<<"]" << endl ; if(polygon_pl >= polygon_pr) return 0 ; ld pl , pr ; pl = max(circle_pl , polygon_pl) ; pr = min(circle_pr , polygon_pr) ; if(pl - eps <= pr) return pr - pl ; else return 0 ; } ld Calc(ld l , ld r) {return (r-l) * (F(l) + F(r) + 4.0 * F((l + r) * 0.5)) / 6.0 ; } ld Simpson(ld l , ld r , ld ans) { ld mid = (l + r) * 0.5 ; ld x1 = Calc(l , mid) , x2 = Calc(mid , r) ; ld al = x1 + x2 ; if(fabs(al - ans) <= 1e-12) return al ; return Simpson(l , mid , x1) + Simpson(mid , r , x2) ; } IL void main() { ld pl = circle_p.x - circle_range ; ld pr = circle_p.x + circle_range ; for(int i = 1; i <= nC; i ++) { pl = min(pl , gc[i].x) ; pr = max(pr , gc[i].x) ; } Ans = Simpson(pl , pr , Calc(pl , pr)) ; printf("%.8Lf\n" , Ans) ; return ; }}int main() { freopen("adieu.in","r",stdin) ; freopen("adieu.out","w",stdout) ; n = gi() ; for(int i = 1; i <= n; i ++) scanf("%Lf %Lf" , &p[i].x , &p[i].y) ; CirCle::main() ; GraHam::main() ; Matrix::main() ; Triange::main() ; Divide_Cut::main() ; Simpson_Int::main() ; return 0 ;}

转载于:https://www.cnblogs.com/Guess2/p/10223751.html

你可能感兴趣的文章
repeater练习
查看>>
BBC micro:bit 学习资源汇总(最近更新2019年1月6日....)
查看>>
QEMU-KVM中的多线程压缩迁移技术
查看>>
Druid的简介
查看>>
JAVA父类引用指向子类的对象意思
查看>>
(贪心)加油站绕圈问题
查看>>
【LeetCode 237】Delete Node in a Linked List
查看>>
C++primer 14.1节练习
查看>>
基于perl面向对象开发的微信机器人
查看>>
组合索引和单列索引效率对比
查看>>
修改一行和修改全表的TX锁
查看>>
genymotion无法下载解决方法
查看>>
理解vuex -- vue的状态管理模式
查看>>
小程序开发之后台mybatis逆向工程(二)
查看>>
Constant, random or timezone-dependent expressions in (sub)partitioning function are not allowed
查看>>
eclipse开发android程序常见问题解决办法
查看>>
一个简单、易用的Python命令行(terminal)进度条库
查看>>
javascript的不一样
查看>>
取球游戏
查看>>
PBKDF2加密的实现
查看>>