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.”