題意：

　　　　給出平面上n個點，問能在其中選出6個點，組成兩個三角形，使得其互不相交

　　　　問有多少種選法

?

　　大致思路

　　　　?考慮枚舉一條直線，將所有得點分為左右兩部分，其中有兩個點在直線上，

　　　　以這兩個點為頂點，分別統計左邊有多少個三角形，右邊有多少個三角形即可。

　　　　枚舉直線時，枚舉一個點，然后對其他點極角排序，
　　　　枚舉另一個點，可快速算出該直線左右兩邊的點的數量(二分，叉積），組合一下即可。

?

　　　　

1 /* 2 : . 3 : 4 i 5 i . 6 i 7 : . 8 i . 9 i . 10 i 11 : . 12 i . i i : . . . . . . . .. . . . 13 . . . . . . . . . 14 : qQ . v2d . i: ..:ij.iBE .i EBj .irrivri.::iiiir7r. . SPd. : 15 i UQB .BBBBE BBBQBBBBLiBB.1BBi :X: BBu . .KBBBBBBBBBBBBBBBQv :BBBBB 16 . iBY PD. BBY vBBv. ..:gB1 rBM 7B1 RQP MBgvPPQBB uRq. .. . jBBQ.BBBr 17 :.BBrQBBBBBL iQBB7:777gBSYvrKBBv:v71r..YPBBBBBBBBBBEBBB 7RBZQdBBBdEgBQE 1QBB1 QBBB: 18 .:BBBBJ.qBBDBBBBBBBvrQBQBBBBBBBBBBBBBgg5UBBBBriiBQ1 rBB .:.:i. :KQBi ..:: :.. . . . ..... UBBB5 UJ: rBBBBXi 19 . IQY i:.:.. YBs :BB IE. XBZ QBs 7BB rBBBBQBBBBBBBQBBBBq BQBBBBBBBBBBBBBBBBviBBE. .BBZ .BBgi. 20 . BBBQSJ.Kb5BQgRBPv :5gQBBBQBB:YBvrBBd QBE BBdiBBBB5 .BB uBs iririiiriir7iii77i. ii .BBD . 21 . uQ5Sv .BB::i::QBU BBQMBK. 7BBBP. DBq QB1 DQ7.L. sBBdQBBMBBBQBBBBBQDi BB5 22 . ...:BB KBJ uB1 UBBBL QBL RQb i:. BBPvi.UBBuY7v7iQBqrrur. BBE . 23 :LBBBBBBJQBBBBQBBBJ :rvBBu:BBB1jBBPbBB SBBZIvSUguJXRBBB: 7QBB BBu .. BBQ 24 r.XX... .QBIYXDJBB1 qBBBBi ir rMQBQ. .sPBBBBBBBBRBBD7 XBBi dB1. . .. .BBg 25 i . . . . . .. ... . 26 : 27 i . . 28 i 29 i . 30 i :r:. 31 i . . vKKSj. . 32 r .. :B: js . 33 i . . rK .S: ::: 34 r :v LS . ibi7gv . 35 i :Ligi .QJ :g7 . 36 . ...5d: . i2Sd rb. vj: . 37 . .7:r27DBi . .Bb: . 7K..Ps 38 uij1Pdr. ri . Sq :Kj7Ii . . :v: 39 UvY: 7P. . . .7 .vIqX. .. . .dBRS7. 40 . . qP . . . .. . . .. :r. .qi :2ZPi 41 . . gs . .:K2 . .irvIs75K5XEKMKgZsD522YLri. iBB1i Pr .2r 42 i iS: .isjjQ. .:rs5KPPMBBBZdBBgi:7Rd7XBBBRSMBBDZQZSr. rDYiiYdQSr. dY 43 : Ys .iXbi. 7: 7v5gQZqPEKXUIjUIdbr ur jRQr1E: .rJgBBDL: iEv .sdD5Yi. MX . . 44 i Si .vU57i .ibQBBgMPI175XUvsq5LBj :Li. jQLJ: . .rdBBQsYL :r1ISv: .gu . 45 : .. iU r5Qu. :sBBD7qDqbbijPj5ISXv22UK .BY . .gSP: .q: rBBBBS . . .7KEYi. qv . 46 . qBsY1i :IqBZqI2rUXLXQPrYjIuED2jZPv. KI . . .BR. rd .bBUBQu. . .isZK1: 5s 47 : vPv. .idDBEP1XYKXQR1r5d2SdPqEDv7IEY Yv . KB.:U. :Ui .BJUBBB1 . rXqIrrB2 . 48 v rQDM1dj7SM1qIuPgXJKS2sKU5urLDMr :Bi . .dBMi7BPYJ 1PKL: BjKIUPBB1 . . :irMX 49 i . .vKDDr1YREIPgv1qS1Qbju1IS2US5vUZBu sr . :BBBBdXMDMgjv. : guJsP7rQgU: JdrsSv: 50 7 rQREJ5u2vuKv5dXKKPXqqXK1PSSqP2USqqBDj . 7QBQRPQriQg:..v7i:. MqEXBs72DQB: .iYYr..iPRJ 51 7 . .MRB221QqKrYSSXdXXuBZuSguL1sPMDQQDPPgBi . :RBBMB5 PELBBBj vP. irRBgRPEv .Ju7ivv7vLi. . 52 : 7DQUdSPqgIqUsKSYv5Si2PrruJSBZR5r:: :Z: .irvX::qPPZMBBQgs .Xs LPuXBBi :Dd2rLsr. . 53 i YBZ7Lg2bUPLb172Xr7PQvJuuuMBbX7. .uRu. :QEBQRRBZgggQBSrY. :SQQX :27:. . 54 i .EP2PX1qJYIPuu5I2g2uB5YXbDZPJ .rr. . 7gZU7r7vYvvvJqBQRBMdgDMgBQQr r5BBr 55 .gB2LgEsPPuKE2IrM5Iu1U2JXgS. :7vvvsYLL7. .rs77JJr. JBQDBbdEZBRgBP . .YIUvirvBQ: . 56 XQQSqgDJ7qg5bPXqLd1bQ2JQB2. ..:7Lv7: iBQSREEBQQRBP: iSPL7. rBu 57 QgUjEE2qJbKsjX2duqYKr5BS. .. .rYr. dBQBZBQBKgM. . rZ2: jEi 58 vJdPIJI5UPSYKb5uLbLSDEu . :BBgBPEBr . .... . iBK. 59 YvLb7K5L7ubsjgJuuSsPQ7 .....:iiirr77v7vrv1PXU77rr::. :E. . .. .. sgi 60 LuKQrsSd5XQPqSij7bBu :ivu5J7i::::::::::i::.::iri.. :Ei. ..i715qLPdUqS. iBi . 61 7UPBv2IPqP1IdXLZZPr . . .sY .ir:. .. .QE .. 62 UsJRubSv7ggUJr1Qg: .. r5 vd. 63 d5YPrSqX7QIvPRBX. . . ..:i777r7vJvr: . .rZ . .iE5rr 64 2LKXj2E17DjSMSQi ..ii7uqS522J7:..... .. 7Z. . .75Y::. 7KdBZEXXBQ: 65 r7PQqdEjJEPJuZJ iIPK1j7:.:. .:i:...... :P .iLuvPSsXQbr .JBP 66 sLPP1uqs2XR7JQ: .:i. .:71ZBBBQEDDMbdMBBBdui: rZ. . bB. 67 UUqK7vSIv5PuDg .YdQBBBBQBMESJ777s1bPdEgRQBBRUi. .5 . .gq 68 vLZPvvbKLdSIBv . 1MBRQBBBMEbZPvgBRJrLY7Uj2J7rvPDQBBgUY722 ... .. iBJ 69 irIKvUPI7M1SRi . . 7BB1JUvSd1Y512IYSBMKLPv1XirsivvUKgDgBBBBBBKr:. .. uE. 70 D2KIJ5D17EPdd. . qBJv.ivivYi7JvrLrLEgbbP1PE:71sS5sDq7vDQD2qbgBBBMJi rR7 71 vJPbvJq2YgEQ2 .BP.L7ijIEuiivr7vii1PKgg5dRjXgUSujJ7JgJ7Piru1UKMBBQM2i .2I:. 72 vrXP1Xg2vJjbL . . sBBuXI1gBgE2SI7vIrrsIiSISdBSEZ1bggQv7Es:U77YLirugggDBBBgKUJrri:.:7IEP. 73 XU1UubPuLu7LY . :5RBgUBBPPdggBEUdqIKXviuJrYdPPq2PKKBqY1jrj75I1LL7UXZBBdPEQBP7jIIdKSBB. . 74 sIDbX5X5KRBSE .ZXLXI7q57UJ5IRUUZP5KZguivSv1S55bS12BMBjJ7dXBgZIqr7dqMEPBEQQ: KB7 ... .. 75 PU7v5MPJ7KZPD iBbU7v77:r7irYdIud5KqZPsrs2vYUsJuPP5SLKgQdEEgdPgMX7qvI5DXbMX :BQ 76 511sSdZXI51vg. . LgXgU77iir5dddBMMBBBP5dP52S2gBQ2vL22RdBQBPQP15SdMR1Jivrr:MBr SBv .jDBMbuv: .. 77 vU52sujjUEq1E. . . 2MrBDU5PQBZP7.:..irDQQPdBBRqi. .:jXQMBPrIjXXBP1iuii.BE .BX rSQK:...i1dX7. 78 KJ1svuqsrEgPK . v1rDQDBj:. .LQBS. .JBE.r7555RbbK55PBr . Kg 7QM. 7BBv 79 PXdEu5PsLKv5di 7E1dKi :J. :gg1iq1LsQRRYuBP .r KQi iBg .2Q5. . 80 IjPP1ID5UJYdBY rBBS . . :BErj7YU5ZPdBZ vBv :Rd IBi 81 2UKK7JPXuIgQBb . bBi . . . . EBPYv7srIKBB vBr sBi . .B1 82 vvbb15d5bSPLPB: . rB: .. . :qBKQvYLJRK iQ2 :ZBBr . Rv . 83 SY57vDIKZLuuKBi .BB. . . . bBXgudD5v .2BBgqqbgBJ . ... .E5 84 v75vYqPPq5KPjJE: . iBBr . .BMvBQEv: BBq1EsSQS5Bi . . :BL 85 vUUs7YuJrXJd7:BP . .PQqv: .. .:77juBQJsi rBQYiJU1JX5PRb: vBL . 86 dZsY55RS1qjdqrBBL .JPMRP77. .:.....:.:i7vjuSqEEbXqqquL7. . .jBQJvdR5vuuuJ5BBq: isBB . . 87 BQ7v1KDu5qYSqsJgQ: .r7IEPUs11uj25X21JJri::... 7QB1rPQY2duIQKXZJ7BBdu7:isDZ5: .. 88 LYRgsvSUPqX1UUI2Bd. ii2MEgI7dRSJ1sSBX7SPXsPZBBXr77. 89 vBB1PBZMQggZDZMXgBBDgMRbbEQQRZPZRPKSPbDRBDKujsuYv25Ys2qSEPDMMddZgZMQBBBgQBQEPsqXJSqsIP52M5UPPsvERZi 90 s5QgPQBIDMMDgDgDgBBgEBBBBBBQQBBBBQBBBBBQQBBBBBBBBQBBBBBQBBBBBBBBBQBBBBBBBMBQgESDDSEKUPgU2qSqUrPBBv. . 91 rrPBBgMDMQRRMQgQDMQBQBMgRQggDgRBBBgZgBBBQBBBBBBBBBBBBBS: ..vbBBBQBQMbSQQMEYSuLI5uPKv1D77PBBXi ... 92 i LdMdKKqqPgZSgd1PZPSLXPXSZZXPZIQZJ5EKdDgMMdqYr.::.:bB: LBXIQBKPgBquP2PZuUuUSXj5ZqXBB7 93 i:BP2j:vYs7q5sZI:2uvv7Ss7UYKs51r51rJLjDg7: .BvPPgX1vrii:2Qi vBbIMQuZrsDP55uu2XYdBQU: . 94 rPBLJ27PXu7SP2QIvSJsPKgYPPisXq1Lg51ZBdr 2Q: .. .qBU.:vbv. :IQBqiSs2KYLudKv7QQb. 95 BBXr7P1PXXsPSjD5757YPPE1JJiXPZj7sSQK: 1v iBu g7 . iDBPQsIPuIP7vZB1. . 96 MuiK7uKKj11Pj:S1UbuJXv2JJSKKLU2rSgX .....:::...::.: .Bd..i.:bj .SB7 .:: KBgMv1gu2KqDBZ: .:ii:ri::iiirrrviii7i. 97 */ 98 99 100 101 #include<cstdio> 102 #include<iostream> 103 #include<cstring> 104 #include<algorithm> 105 #include<queue> 106 #include<set> 107 #include<map> 108 #include<stack> 109 #include<time.h> 110 #include<cstdlib> 111 #include<cmath> 112 #include<list> 113 using namespace std; 114 #define MAXN 10000006 115 #define eps 0 116 #define For(i,a,b) for(int i=a;i<=b;i++) 117 #define Fore(i,a,b) for(int i=a;i>=b;i--) 118 #define lson l,mid,rt<<1 119 #define rson mid+1,r,rt<<1|1 120 #define mkp make_pair 121 #define pb push_back 122 #define cr clear() 123 #define sz size() 124 #define met(a,b) memset(a,b,sizeof(a)) 125 #define iossy ios::sync_with_stdio(false) 126 #define fr freopen 127 #define pi acos(-1.0) 128 #define Vector Point 129 #define fir first 130 #define sec second 131 #define it_s_too_hard main 132 const long long inf=1LL<<62; 133 const int iinf=1<<30; 134 const double dinf=1e17; 135 const int Mod=1e9+7; 136 typedef long long ll; 137 typedef long double ld; 138 struct Point{ 139 ll x,y; 140 double ang; 141 Point(ll x=0,ll y=0):x(x),y(y) {} 142 Point operator - (const Point &a)const { return Point(x-a.x,y-a.y);} 143 }; 144 ll Cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x;} 145 int n; 146 Point o; 147 Vector v1,v2; 148 bool cmp(Point a,Point b){ 149 return a.ang<b.ang; 150 } 151 Point p[2050],tp[5050]; 152 void I_can_t_solve_it(){ 153 cin>>n; 154 ll ans=0,cnt1,l,r,ct; 155 For(i,1,n) cin>>p[i].x>>p[i].y; 156 For(i,1,n){ 157 For(j,1,n) { 158 if(j==i) continue; 159 if(j>i) tp[j-1]=p[j]-p[i],tp[j-1].ang=atan2(tp[j-1].y,tp[j-1].x); 160 else tp[j]=p[j]-p[i],tp[j].ang=atan2(tp[j].y,tp[j].x); 161 } 162 ct=n-1;cnt1=1; 163 sort(tp+1,tp+ct+1,cmp); 164 For(j,1,ct) tp[j+ct]=tp[j]; 165 For(j,1,ct){ 166 if(j>cnt1) cnt1=j; 167 if(cnt1>ct*2) break; 168 while(cnt1-j+2<=ct && cnt1<ct*2 && Cross(tp[j],tp[cnt1+1])>0) cnt1++; 169 l=cnt1-j;r=n-1-l-1; 170 ans+=l*(l-1)*r*(r-1)/4; 171 } 172 } 173 cout<<ans/2<<endl; 174 175 } 176 int it_s_too_hard(){ 177 int t=1; 178 iossy; 179 For(i,1,t){ 180 I_can_t_solve_it(); 181 } 182 return 0; 183 } View Code

?

轉載于:https://www.cnblogs.com/cjbiantai/p/9521392.html

總結

以上是生活随笔為你收集整理的[CodeForces]CodeForces - 1025F Disjoint Triangles的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。