HDU3548 Enumerate the Triangles(优化)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 #define INF 1001*1002
 8 struct point{
 9     int x, y;
10 }p[1005];
11 bool cmp(point a, point b){
12     return a.x == b.x ? a.y < b.y : a.x < b.x;
13 }
14 double dis(int i, int j){
15     return sqrt( 1.0*(p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y) );
16 }
17 int main()
18 {
19     int i, j, t, r, n;
20     double IJ, IR, JR, C, minC;
21     int cas = 1;
22     cin>>t;
23     while(t--)
24     {
25         cin>>n;
26         for(i = 1; i <= n; i++)
27             scanf("%d%d", &p[i].x, &p[i].y);
28         C = minC = INF;
29         sort(p+1, p+n+1, cmp);
30         for(i = 1; i <= n; i++){
31             for(j = i+1; j <= n; j++){
32                 IJ  = dis(i, j);
33                 /*周长c=L1+L2+L3，所以推得c > 2Li，假设Li的端点为点a、b，
34                   则又有Li>=| Xa-Xb |，故c > 2*| Xa-Xb |*/
35                 if(minC <= 2*(p[j].x-p[i].x))break;//优化②
36                 if(minC <= 2*IJ)continue;//优化①
37 
38                 for(r = j+1; r <= n; r++){
39                     if(minC <= 2*(p[r].x-p[j].x))break;//优化②
40                     IR = dis(i, r);
41                     JR = dis(j, r);
42                     if(IJ + IR > JR && (fabs(IJ-IR) < JR))
43                         C = IJ + IR + JR;
44                     minC = min(C, minC);
45                 }
46             }
47         }
48         printf("Case %d: ", cas++);
49         if(minC == INF)printf("No Solution\n");
50         else printf("%.3lf\n", minC);
51     }
52     return 0;
53 }