Magical Triangles
2021/7/11 23:36:50
本文主要是介绍Magical Triangles,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Magical Triangles
Preface
For thousands of years, people have been attracted by the magic of triangles. From the ancient Greek period when humans began to explore the mystery of the world, to the darkest times of the Middle Age, the magic of triangles is multiplied in this modern civilization which is filled with technologies and information.
With both fear and curiosity, I was puzzled by such a beautiful problem. From the triangles overlapping together, I was just feeling like seeing the whole appearance of the so lasting mystery in this amazing world of Geometry.
[COCI2009-2010#6] XOR
https://www.luogu.com.cn/problem/P4515
Section I: Ideas Forming
“To pursue what is unlimited with what is limited is an exhausting undertaking.”
Right-angle triangles are up and down the picture, like peaks in the deep green mountains at the border of the world. Before I learnt the secret to this problem, the peaks were continuous in my eyes. But they needn’t to be.
When Pao Ding first began to cup up an ox, what he saw was no more than a whole ox. But years later, no more whole ox were seen. He dealt with the ox in his mind, and saw every single part of it.
Why not slice the mountain into pieces, instead of calculating the peaks struggling with the complex relationship between them?
Section II: Further Details
“I take advantage of what is already there.”
We define the vertexes of the triangles and their intersections as KEY POINTS. It is obvious that we can wisely slice the picture by the abscissas of the key points.
In the example below, we do such things like this:
Now what we only need to do is calculate the valid areas between every two lines. It is not difficult to notice that every part of a valid area here is a trapezoid (triangles and parallelograms are also considered trapezoids).
This is what comes to our mind:
S=(a+b)*h/2
A good butcher changes his knife once a year, for he uses his knife to slit; an ordinary butcher changes his knife once a month, for he uses his knife to hack.
To save time, we must find a good way to check if a trapezoid is valid. Great observation! The valid trapezoids are spaces, and so are the edges of the trapezoids. That is to say, after a ‘useful edge’, there is a ‘useless’ one. Why is that happening? Because every time we go past a point, the color of the string changes once.
What a beautiful conclusion! Now it is easy to calculate the sum of a and b in the formula S=(a+b)*h/2. Obviously H here is the distance between the two parallel lines we are considering.
Then we can get every S. The answer is in front of our eyes.
Section III: Coding
“There is certainly plenty of room for the blade of my knife without thickness to enter the joints where there are crevices.”
Here is my AC code. It really took me some time.
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 inline int read(){ 6 int res=0,f=1;char c=getchar(); 7 while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();} 8 while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar(); 9 return res*f; 10 } 11 12 #define N 1005 13 struct tri{ 14 int x,y,r; 15 }; 16 tri t[N]; 17 18 int p[N],tot; 19 20 inline void jiao(tri a,tri b){//hypotenuse of a, right angle side of b 21 if(b.y>=a.y+a.r||b.y+b.r<=a.y) return;//outside the range of the right angle side of b 22 int len=a.y+a.r-b.y; 23 int xx=a.x+len; 24 if(xx>b.x&&xx<b.x+b.r) p[++tot]=xx; 25 } 26 27 int s1[N],s2[N],cnt; 28 inline void intersections(int x1,int x2,tri a){ 29 if(a.x+a.r<=x1) return; 30 if(a.x>=x2) return; 31 int l1=x1-a.x,l2=x2-a.x; 32 s1[++cnt]=a.y+a.r-l1; 33 s2[cnt]=a.y+a.r-l2; 34 s1[++cnt]=a.y; 35 s2[cnt]=a.y; 36 } 37 38 int n; 39 ll res; 40 double ans; 41 42 int vis[N]; 43 int main(){ 44 // freopen("data.in","r",stdin); 45 // freopen("me.out","w",stdout); 46 n=read(); 47 for(int i=1;i<=n;i++){ 48 t[i].x=read(); 49 t[i].y=read(); 50 t[i].r=read(); 51 p[++tot]=t[i].x; 52 p[++tot]=t[i].x+t[i].r; 53 } 54 jiao(t[5],t[1]); 55 for(int i=1;i<=n;i++){ 56 for(int j=1;j<=n;j++){ 57 if(i==j) continue; 58 jiao(t[i],t[j]); 59 } 60 } 61 sort(p+1,p+tot+1); 62 tot=unique(p+1,p+tot+1)-p; 63 for(int i=2;i<=tot;i++){ 64 // cout<<p[i]<<endl; 65 cnt=0; 66 for(int j=1;j<=n;j++){ 67 intersections(p[i-1],p[i],t[j]); 68 } 69 sort(s1+1,s1+cnt+1); 70 sort(s2+1,s2+cnt+1); 71 res=0; 72 for(int j=1;j<=cnt;j++){ 73 // cout<<s1[j]<<' '; 74 if(!(j&1)) res+=s1[j]-s1[j-1]+s2[j]-s2[j-1]; 75 }//puts(""); 76 ans+=res*(p[i]-p[i-1])/2.0; 77 // cout<<res*(p[i]-p[i-1])/2.0<<endl; 78 } 79 printf("%.1lf\n",ans); 80 return 0; 81 }
The End
Secrets can always be seen by people with wisdom and a peace heart.
Thanks to my teacher and my friends. Without their help, I couldn’t have done this.
“Good! From the words of a butcher I have learnt the way of nurturing life.”
这篇关于Magical Triangles的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享
- 2024-12-24uniapp 连接之后会被立马断开是什么原因?-icode9专业技术文章分享
- 2024-12-24cdn 路径可以指定规则映射吗?-icode9专业技术文章分享
- 2024-12-24CAP:Serverless?+AI?让应用开发更简单
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理,增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享