cppcodes/circle.cpp at master · jindalshivam09/cppcodes · GitHub

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

  /*  U_x = ((A_x^2 + A_y^2)(B_y - C_y) + (B_x^2 + B_y^2)(C_y - A_y) + (C_x^2 + C_y^2)(A_y - B_y)) / D,
    U_y = ((A_x^2 + A_y^2)(C_x - B_x) + (B_x^2 + B_y^2)(A_x - C_x) + (C_x^2 + C_y^2)(B_x - A_x)) / D

with

    D = 2( A_x(B_y - C_y) + B_x(C_y - A_y) + C_x(A_y - B_y)).\,
 */

 #include<iostream>
 #include<iomanip>
 #include<cmath>
 using namespace std;

typedef long long ll;

pair<ll,ll> circumcenter(int x1,int y1,int x2,int y2,int x3,int y3) {
    ll x,y;
    //cout << setprecision(6);
     x = ((x1*x1 + y1*y1)*(y2-y3) + (x2*x2 + y2*y2)*(y3-y1) + (x3*x3 + y3*y3)*(y1-y2)) ;
     y = ((x1*x1 + y1*y1)*(x3-x2) + (x2*x2 + y2*y2)*(x1-x3) + (x3*x3 + y3*y3)*(x2-x1)) ;
    //cout << x << " " << y << endl;
    return make_pair(x,y);
}

bool isCollinear(int x1,int y1,int x2,int y2,int x3,int y3) {
    return (y2-y1)*(x3-x1) == (y3-y1)*(x2-x1);
}
ll calD (int x1,int y1,int x2,int y2,int x3,int y3) {
    return 2*( x1*(y2 - y3) + x2*(y3 - y1) + x3*(y1 - y2));
}

main(){
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        int cord[n][2];
        for(int i=0;i<n;i++)
        cin >> cord[i][0] >> cord[i][1];
        //ll tot =
        //cout << setprecision(8);
        int count=0;
        int tot=0;
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                for(int k=j+1;k<n;k++) {

                    if(!isCollinear(cord[i][0],cord[i][1],cord[j][0],cord[j][1],cord[k][0],cord[k][1])) {
                        pair<ll,ll> c = circumcenter(cord[i][0],cord[i][1],cord[j][0],cord[j][1],cord[k][0],cord[k][1]);
                        ll d = calD(cord[i][0],cord[i][1],cord[j][0],cord[j][1],cord[k][0],cord[k][1]);
                        //cout << c.first << " " << c.second << endl;
                        ll x = c.first , y = c.second;
                        //cout << x << " " << y << endl;
                        ll radius = ((x-d*cord[i][0])*(x-d*cord[i][0]))+((y-d*cord[i][1])*(y-d*cord[i][1]));
                        for(int q=0;q<n;q++) {
                            if((cord[q][0]!=cord[i][0] || cord[q][1]!=cord[i][1])) {
                                if((cord[q][0]!=cord[j][0] || cord[q][1]!=cord[j][1])) {
                                    if((cord[q][0]!=cord[k][0] || cord[q][1]!=cord[k][1])) {
                              //          cout << cord[i][0] << cord[i][1] << endl;
                                //        cout << cord[j][0] << cord[j][1] << endl;
                                  //      cout << cord[k][0] << cord[k][1] << endl;
                                    //    cout << cord[q][0] << cord[q][1] << endl << endl;
                                        //cout << radius <<  " " << ((x-cord[q][0])*(x-cord[q][0])+(y-cord[q][1])*(y-cord[q][1])) << endl << endl;
                                        if(radius >= ((x-d*cord[q][0])*(x-d*cord[q][0]))+((y-d*cord[q][1])*(y-d*cord[q][1])))
                                        count++;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
      //  cout << count << " " << n << endl;
        cout <<setprecision(7) <<  (float)(count*6)/(n*(n-1)*(n-2)*(n-3)) << endl;
    }
}