1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define INF 100000000 7 #define eps 1e-9 8  9 const int MAXN = 1000;10 11 int n;12 double dp[MAXN][MAXN];13 14 struct Point{15     double x, y;16 17     friend Point operator + (const Point A, const Point B){18         return (Point){A.x+B.x, A.y+B.y};19     }20 21     friend Point operator - (const Point A, const Point B){22         return (Point){A.x-B.x, A.y-B.y};23     }24 25     friend Point operator * (const Point A, const Point B){26         return (Point){A.x*B.x, A.y*B.y};27     }28 29     friend Point operator / (const Point A, const Point B){30         return (Point){A.x/B.x, A.y/B.y};31     }32 }p[MAXN][MAXN];33 34 inline Point make_Point(double X, double Y){35     return (Point){X, Y};36 }37 38 inline double len(Point A){39     return sqrt(A.x*A.x+A.y*A.y);40 }41 42 inline bool In_region(double eg, double l, double r){43     if (l>r) swap(l, r);44     return (l-eps<=eg && eg<=r+eps);45 }46 47 inline bool Connected(int I1, int I2, int I3, int I4){48     if (I1>I3) swap(I1, I3);49     if ((I1==I3 && I2==I4) || I3-I1==1) return true;50     double k = (p[I1][I2].y-p[I3][I4].y)/(p[I1][I2].x-p[I3][I4].x), b = p[I1][I2].y-p[I1][I2].x*k, bn;51     for (int i=I1+1; i<I3; i++){52         bn = p[i][0].x*k+b;53         if (!In_region(bn, p[i][0].y, p[i][1].y) && !In_region(bn, p[i][2].y, p[i][3].y)) return false; 54     }55     return true;56 }57 58 int main(){59     scanf("%d", &n);60 61     p[0][0] = p[0][1] = p[0][2] = p[0][3] = make_Point(0, 5);62     p[n+1][0] = p[n+1][1] = p[n+1][2] = p[n+1][3] = make_Point(10, 5);63 64     double x, in, apl;65     for (int i=1; i<=n; i++){66         scanf("%lf", &x);67         for (int j=0; j<4; j++)68             scanf("%lf", &in), p[i][j] = make_Point(x, in);        69     }70 71     //init72     for (int i=0; i<4; i++)73         dp[0][i] = 0.0;74     for (int i=1; i<=n+1; i++)75         for (int j=0; j<4; j++)76             dp[i][j] = Connected(0, 0, i, j) ? len(p[i][j]-p[0][0]) : INF;77 78     for (int i=0; i<=n+1; i++)79         for (int j=0; j<4; j++)80             for (int k=0; k<i; k++)81                 for (int l=0; l<4; l++)82                     if (Connected(k, l, i, j)) dp[i][j] = min(dp[i][j], dp[k][l]+len(p[i][j]-p[k][l]));83     apl = INF;84     for (int i=0; i<4; i++) 85         apl = min(apl, dp[n+1][i]);86     printf("%.2lf\n",apl);87     return 0;88 }

 1 #include <cstdio> 2 #include <iomanip> 3 #include <iostream> 4 #include <algorithm> 5 #define eps 1e-12 6 using namespace std; 7  8 const int MAXN = 100001+10; 9 10 int n;11 12 struct Point{13     long double x, y;14     15     friend Point operator - (const Point& A, const Point& B){16         return (Point){A.x-B.x, A.y-B.y};17     }18     19     friend long double operator * (const Point& A, const Point& B){//cross20         return A.x*B.y-A.y*B.x;21     }22 23     friend bool operator < (const Point& A, const Point& B){24         return (A.x!=B.x) ? A.x<B.x : A.y<B.y;25     }26 27     inline void print(){28         cout<<setiosflags(ios::fixed)<<setprecision(4)<<x<<" "<<setiosflags(ios::fixed)<<setprecision(4)<<y<<"\n";29     }30 }p[MAXN], ch[MAXN];31 32 inline int dcmp(long double eg){33     if (eg>eps) return 1; //>034     if (eg<-eps) return -1;//<035     else return 0;36 }37 38 inline void GrahamScan(){39     int tot, t;40     sort(p, p+n);41     42     ch[0] = p[0], ch[1] = p[1], tot = 1;43     for (int i=2; i<n; i++){44         while (tot>0 && dcmp((ch[tot]-ch[tot-1])*(p[i]-ch[tot-1]))!=-1) tot--;45         ch[++tot] = p[i];46     }47 48     t = tot, ch[++tot] = p[n-2];49     for (int i=n-3; i>=0; i--){50         while (tot>t && dcmp((ch[tot]-ch[tot-1])*(p[i]-ch[tot-1]))!=-1) tot--;51         ch[++tot] = p[i];52     }53 54     for (int i=0; i<tot; i++)55         ch[i].print();56 }57 58 int main(){59         scanf("%d", &n);    60         for (int i=0; i<n; i++)61         cin>>p[i].x>>p[i].y;62 63     GrahamScan();64     return 0;65 }

 1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 #define eps 1e-9 5 using namespace std; 6  7 const int MAXL = 1000; 8  9 struct Point{10     double x,y;11 12     inline void in(){13         char s[MAXL];14         scanf("%s",s);15         int i;16         x = 0,y = 0;17         for (i=1;;i++){18             if (s[i]==‘,‘) break;19             x *= 10,x += s[i]-48;20         }21         for (i+=1;;i++){22             if (s[i]==‘)‘) break;23             y *= 10,y += s[i]-48;24         }25 26     }27 28     inline void out(){29         printf("%.2lf %.2lf\n",x,y);30     }31 32     inline bool is_zero(){33         return (y==0 && x==0);34     }35 36     inline double len(){37         return sqrt(x*x-y*y);38     }39 40     friend Point operator + (const Point A,const Point B){41         return (Point){A.x+B.x,A.y+B.y};42     }43 44     friend Point operator - (const Point A,const Point B){45         return (Point){A.x-B.x,A.y-B.y};46     }47 48     friend Point operator * (const Point A,const double B){49         return (Point){A.x*B,A.y*B};50     }51 52     friend Point operator / (const Point A,const double B){53         return (Point){A.x/B,A.y/B};54     }55 56     friend bool operator == (const Point A,const Point B){57         return (A.x==B.x && A.y==B.y);58     }59 }A,B,C,D;60 61 inline double area(Point p1,Point p2,Point p3){62     return abs(0.5*(p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x));63 }64 65 inline bool on(Point Aa,Point Ba,Point q){66     double MX = max(Aa.x,Ba.x);67     double mx = min(Aa.x,Ba.x);68     double MY = max(Aa.y,Ba.y);69     double my = min(Aa.y,Ba.y);70     return ((mx<q.x && q.x<MX) && (my<q.y && q.y<MY)) ? true : false;71 }72 73 inline bool zero(double eg){74     return (eg>-eps && eg<eps);75 } 76 77 inline int appleeeeeeee(){78     A.in();B.in();C.in();D.in();79     if (A==D || B==D || C==D) return 4;//顶点上80     double s1,s2,s3,s;81     s = area(A,B,C);82     s1 = area(A,B,D);83     s2 = area(A,C,D);84     s3 = area(B,C,D);85 86     if (zero(s1) && on(A,B,D)) return 3;87     if (zero(s2) && on(A,C,D)) return 3;88     if (zero(s3) && on(B,C,D)) return 3;//边上89 90     if ((s1+s2+s3-s)<eps && (s1+s2+s3-s)>-eps) return 1;91     else return 2;92 }93 94 int main(){95     printf("%d",appleeeeeeee());96     return 0;97 }

 1 #include <cstdio> 2 #include <cmath> 3  4 struct Point{ 5     double x,y; 6  7     inline void in(){ 8         scanf("%lf%lf",&x,&y); 9     }10 11     inline void out(){12         printf("%.2lf %.2lf",x,y);13     }14 15     friend Point operator + (const Point A,const Point B){16         return (Point){A.x+B.x,A.y+B.y};17     }18 19     friend Point operator - (const Point A,const Point B){20         return (Point){A.x-B.x,A.y-B.y};21     }22 23     friend Point operator * (const Point A,const double B){24         return (Point){A.x*B,A.y*B};25     }26 27     friend Point operator / (const Point A,const double B){28         return (Point){A.x/B,A.y/B};29     }30 }a,b,c,d;31 32 inline double len(Point eg){33     return sqrt(eg.x*eg.x+eg.y*eg.y);34 }35 36 int main(){37     a.in();b.in();c.in();38     b = b-a,c = c-a;39     double AB = len(b),AC = len(c);40     double cj = (AB*AC)/(AB+AC);41     d = b/AB + c/AC;42     d = d*cj;43     d = d + a;44     d.out();45     return 0;46 }