参考:http://blog.****.net/libin56842/article/details/26618129
题意:给一个正多边形内点到其他顶点的距离(逆时针给出),求正多边形的边长
二分多边形的边长
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAYQAAAF1CAIAAABnEQo4AAAUaUlEQVR4nO2Z23UcSQ5EaZcMoj2yRs7ImN6PnsOl2F1VWZl4BJD3fs6ShUAEMrSa+XgAAAjwkS0AAODxoIwAQATKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCAAkoIwAQALKCC74WCZ7A6gBhwKPh0XjUFKwCAexHSm9M0i2N5AJ8fcnu2GWyDYP4iDsnmR3iAvZpoIvBNyHmPfv8SsmwqA6hFqeyLed8jWTWaAPWVYl/vUGTJleamUvEIEIi5HyULMKImUoZEFyNUh8kyffV5ARMBpiIDB1cp/f+SA1VTHTwQmiEiX9sY1MVCiFdAFgBQnJofC6xie+/YGUOkg3DRYhGyFEntOtuUc/oyY+WAZMQCoSiLyfieknP5ZbBCOWhomBEQgjGZ0HMz39/OfTW0DHYTiHGHJQeyErGi5/RXlBKkkHAohG8FUsyhj5LfFNqSQFsD4UtZdgImPw1/W3po9ywfcgBB+AoZLxL+ivTyVlgePuaB69rZhbHynhA5UUD177InjoHnrufkfKkBM99FEkGO2F5n376Zn4YBVzqKQYsNge2Zt2lTT3zUIupQtrD+YaI3vH3qqmP1vLrnRhjcFZM07ON/eCYyStfLyWb+nCuoKnNshebaSqxRG1DEwX1g8MNUD2WIOFrU/ByZ3BzSVk/9hMUWUyS9PPE2EK2nqAj/PInmaWMMOJeLshmDiJ7FHmCjMcisO7gYO3ObrF9HNUEGY7N32du8IUtNUF7+4he4Iiwjymi6xWSFhRMO4GsscnJYw+UhBWEVwbRfbs1IQ5yVBbU19YObBsCM1r03wGfmKO9k1f+URbtq5KYNYFskdWSJj392UXFxFWBZw6Q/a8ZIU98VYlu76ssBJg0yGah6Wp6gcB2mR9kBWmDx69R/OkNFW9EiZP1hBNVeJg0Bs0L0n24b0SKVLWFk1VyuDOTwRv6Oi9pQs7IVKnrDmaqmTBmn8QvB7Zl3ZOsNojl9KNEpQkC778H8G70XxgI6QI1rRLUJImmPIfghej+bTGoY/OVeVKEgRHHg+9W9F8UXfJEq/pnqAkNbBD7ko039IEufoFbVTTo8buXqjdh+ATmiZ9C0Ez1fRIsbURUpdx9HJKH2v6IoKWqunRYV8XpG5C8M2YoLDOkbdqcWeJ0WFfC3SuQe2pGKKzkZrJUmJE2HR/kTs4eiFt7lJqLzWrdZSIsOP+Ikeg9jackNpOzXMdJQpst7zILaq9Cj8EF5QyX0SGAnttLnKCUo/BG80ddSIQkaHARmsrpK7zBiLRXFYnCxEZ6Wy0c3reOtcfjOy+R4ko3EawAAV22Tk9bJGjT0F8ZZFo0gWks8XCuTEf3fo+16a/uEhA6QJy6b9t7pGJXHk6+usrJJUuIJf+q9JEClRxID2yna+l+apZ0R7d9Fa39Z1CJqQHt+3NdN5TrYlipmtSy430BGvZZUXbJbOOKf2OZallyFGOiVcUMDeXthvq3NAOZzRCRU+k+ihgaC49N4wPkhq6pKgz9FEYDdejiWQp6g99FEPD3YLzo4nGKW1RStBb3VW33SLDO7rO3hezQnWX6CNXui0Wlhw1NEEDuxT6yHVWIq0Wo4n0aeDYUfqR9+Y0KJc+W8UEFn+IzWhjGn1kTp+VAtKihtbpZF3kPexwdU1Woomq0MxA+siQJvvQRIXo52HYefSz7jsd9nE9AmrInJZOxtxJ7zssvwxNVI6uZtJHi5TfxC8bmsiPrpYe3YzrWVp9OZ3amzgFE3BSm9PbVfpojtpreKRCDQXQ3tvgPrL6bC6116CJirKDw6631NLAwjvY5nF0Oj1iFmQTk52OquWVFt4hoImspMIr+1hNHw1SdQHDJGiiFLZy2+PG+l1s1QVoogbs5rn5sTUzsOQCJnFSQ+ls6Lzt1TW73pLqaaIe7Gm+ax/ZSg2mnvr1FGkiEbb1/+gCTY7ZQ3AM9aSvWG94BGDCzik49ZGH1BiKSV9JjhoSZPMsTG6yzUkX000TNYM4PPrISao3xXRPmH4Udt3MOkEoTxZPtIeNlUQbNpG3VBiHaJ7Y9pGrVCcqib5rN01UAtL5YuViG9hYRvTdhGiiKhDQd47uduLgYwQbUkbxuNHUUDlI6gcmfRQj1ZAyigeNpokqQlivTFxydRtrKB6MhCYqCnm95e49V7/8GnIvLT6KrVwee0JqJ9w67NI21pB7bjE11ACyO2H8wkvbWEDueQY0UQ+I75wd+qiAVppoB0jwEsoonyNzqaFOEOUlc2VUyEl1oSe2vs2mkPXwA3I84da1F3VSXehEGdUKAL4gwSPuHnlRJ9WFntt63keFYoBH2ScUAGUkwYitVFIbCO6VicMu+gSkVY4betlHVfLYHCL7wfQ9V3RSWqVtGRVKZVsI6zsrl1zRSWmVHmVUKJsNIanvUEYqrLtPJVWEjJ4snm7Fa9eVuOj+0T+vGNJWkM7D6GjLOakr0aqM3v6v5XLaB6J5UEZqmLtvEjB4Qy6Xh0oZheLnPpWkz86JvD3IaUNqOSmqb87E8d+ikpTZNoujU6SMMjEpo8tfpJI02TaFkSaijKKJdJ9KEmTDCI4Ob8WKWjaK6osso7e/SCXlspv5J/dGGSVj2Ckrc6mkLLay/eTS1i+wkJOK4tLdp5LS2crzk2XNj9lOtT2K4tLL6O13tnoeCmzi9vldUUbJ2JbRYgBUUhY7+Hx5TpRRMoIBUEnxtHf48pBMHChko6I4wTJ6+1kqyZX29l4uSBnlI1tGbz/e/s0k0tjYkbOhjJLxCMAjAyopgK6WTjTRyvpVbJRTVisAKsmVrmZOlJHhuJVPuSKnrFYZvZ1FJRnSz8nB86CM8nEqo4AMqCQPmnk410SUUQ7VM6CPbOlk4PhJ2G5dxUM5ZdXL6HUulbRCJ/fGd6GMJPAro+AYqCQrevg23USUURrNYqCS1mng2K3czfetYqCWsq4xUEkrVPfqbuJdX8ElWsp6x0AlzVHdqLv6PZYt4Z6WMu8YFJKgkiaoa9FiE3V9BW/RkrVPDFTSLYqaMxGr06YlDNSStU8ZPaGSBqloy1yglJEKAWUkmASVNEI5T9abiDLKZOskqKRTarkxF5/fjiXc05K1cxk9oZKOKOTDdGqUkRAxZSQbxhdU0itVTJjOy3XBGtZlC/iHzcP4AZX0gxLrT8fkul0N67IF/ANl9AqV9IX+4ivpUEZassLKSDaPI6ikh/yLWgyFMtKSRR7nUEnK+67E4b2Xsm9faMmijEbYuZJkN11MgTJ6UEZ12bOSNHdcN58yeuxcRrKR3GK3PhJccN35gOAEfXtFSxaRTHDeR23W/EJtu3XDAzZSM+0tWrIoo2n2qSSpvUx8poyeaMkKLiPZVKbZoZJ0NvJoIspIBVIxoXcliaxjZWzMLgqOXaIlizIypHElLS7y9/evj4+PX7//GmqY9pMy+kJLVnwZyQZjRctKWlvh7+9fH5+fnyttZGhjfBk5jVhHTllwMMrZGNKskpbE//n8+Pj88/f3r4+Pzz8G02s1kXLWcsoCjKuSjTmdKmla+bOL/vu72v02svWNMvqOnDLKyJselTSp+VsF/f39a+JfHNnaRRl9R04Z8cRQvZLm1P7zf4fut5FrE3HtcsqIJ5K6lTQl9c/nx/e/mj3/q9roX9XMzQmzukym2QJ+QhnFU7SSbov88/l2u5E28rAlzOQSaT4oI/2EwjhqIlmLbsp7+7ey0b+qeTcRZfTYtowiB9WiUCXdE3b0X8/+fF62kYcJka7KJvgDOWWUkQIlKumWqh//umjof7k/ZRzK6BVFZTHeaT4wKfQrKUCPx9aRTqpFdoKiOHKSQrmSvJU4LRtpoE5YlyiKo4wE0awkVw1+O1JGb1EUl1VG4lEpsE8fuS5IGb1FURxRKXPeR/EehpWR/pdHxrnOWkRRHFHpo1NJHnNd1wk2qtCFi4oLc7BQVIIoVJL5UO8tKKMjRMVllZF4WpqkV5LhOG/9webUum1RfQRWjsRKuhy9gqtU24+nj1tEVF+kibUCEyf4bQ8OncZbqvn3c8ctIqov0sSAE9yN4Ed+p15uYCvyrU7zEecTvcctIqovOLZamVUh8rUPN8wNDOW9FWn+fYWJK+jqi/SxVma1iHnzN3vmGhNV5yI9RiSOW0dXYqSVMbe4M96Pf+VrYelTRufoSiS5frhW0tynujZRysRFdCWGXcnbca6zNsepkiY+YjjdQ57huBInLS2RMmqMeSWZlNH9PRzlFRpngrRK8muPYSXd/d3EJuKY3yKtkvw2waqSxn9rZcoE8adV8ZilVUaey+s411nwynolrZSR3R5LwjzGVTlmdZWJF1MlwmasVNLgT+Y2UXwZeY+zQl0oKe7JXB+N/OQO1VD0jNWFtr8bOOK8j47SOf+Z8e/4LeI9LmWiCQWERjobf6lwzt1KultG8fr7TbSigNDcLL3HwQjjlXQSX8or3WGiFQW0Bt9Q3SzbM1hJI/8wLFnKaJwaWikj+OKykl4TPPrn8WqbjbOlhlwShR8sllGWyOCJ3uNsqSE3ONTSiW7FeCWlBJrbROVOt4xcygiOoIxSxplTRnFiGVXMdUPUyih+bvWjLaM4ONrquW7LZQ1llVHwuIpHW0kxZQQjnPfRJmXkPc6DSqITy6hounuSXkNvNQRP9B7nQSXRwQE3SHdPTsooLMfcJip6rsVEU0ZwwnkNRUaZW0be45wopjvysHr8abMJgzXUsozaHGo93Ykxu86COW7VUMuzaXOl9aRHHlabmFtyq3S6llHkc/CmpHTKaHNu1dDbX4mU12aWNyXVh/1pEDYIRhjpoKOMWt5Ms/usqj4rb79BcMJ0B518JEaq05S3s6rfZ1X1YTF0CrsiJjX09lMxgp2mvA5qcJxVF8gqowaRV8Gwho4+GKDZfETKrBgKL5DVR05T4MlIB02nEFxG5t/PmhVD4R0oo2b4ddDRCBPZkd8/GtTjLGvvkFJGPYKXIqCGjgaZfDbg4+ez/AZFUnuNsPhbZq9AWA0dTSzx5fNBbQ6y/BoxwbTMPpGRDioXZcyRdG2iB2U0N8VjxCZkddCJAKcvW332fEqna+ywCX1UgvQaOlLi8c2YI2x2h02WoYyU0amht3pkv3k5pdkdNlkmIKTGR+CHWg0dqTL/5voHL0f0O8I++3hH1f4UDBnpoFwDbZUErCblnhN9Voo/CPPvN0C8g75wLSMThecjRGy0pdVK3oG1v4YVqtTQF4bavNcUd9KKbltFllHXm7hLuRp6YqUwYFl9M03otpj3ZWxyFiOMdJCyRVZSg5tI2dJFGi7mGt4mZ3FO6Q76jn4ZFTV2joa7RZZR7+N4pU0NPaGMpOi5W2QfGX5ZmWY19GR9BZrIkLbr+QW5132MkS1zHtky6mTyIG039Hszm5xI7w76QrOMurp9TucNY8qo35VsUkNPVlbzs6Wx4Sc0XzKmj0y+qcBWNfSFVRk56Wnp+Vv67+kRbb9b2bOGnkiV0T62v9J/VY931eZiRjqo7naDzO3r5NJu5n9ni1U9Aq5+MXTQd9bLyEPGVhE8Nimjh0PMdY+GGnpFoYxIYaOFbcOueDrU0BETPtj6RhaPzcvIto+sdJoz0kHK+mO45QZN5MFeO9umrn89dNA4UmW0+MGibLf2JmVEDU0w7o+hk+TyxY6b9+4jamiaQZf87mfzaDZd3uoIdC5ppIM2v/VL5srIahwBbbq81R0oXBIdZMiIbybeEtMr++5vcg2590QNmXPpnonDJPWWrS3w6CMPnZdDOW4rLm2kifzY3YX1y4i8qpEO4rIXcS0j8joBI1bvI+a2qKEwTixdNJzIzsGLx8O6jwK0cdB+nNhLE7mCHf+xcitOF0YNZWFeRmQ3Ao78n+mLMb8zaigX2zIivkEw5R+s+shwOnccz1vPTQ6DBE/Al5/MXc/itdFBalyW0cRHyPEcrHnDxA1NHxw1pMl6GRHlXXDnPXcvaeLsqCFlFqMhzQkw6JC7Vzj3Y9SQLDRRMHh0xq1bvPwZOqgWEzER6wrYdMH4eZ38DDVUkbthkewiOHXNdB+d/zrHqg9NFAlmjTJybXfLKGMPuMFgauRrAn7d4PLmTnoH2nDrJGAcXLvH5fH53D+ocOsY4BYYd5vzS3W4fxBi5AZgDrybJOz6QYqT6LNPsjw4OE/kGwAFTkLPPsYOYOIS54cLnSBrb/DRAG60PUQcAG7awB+bXSHZMDDUjJOr5XArQqDB4KkxnG8PyDEenLWHP1FLQ3xZYK4X3HQ5iCwXLPaF+64CMaWD0e6c9xG3ng7piIDXQVBJapCIGjgeCg9AgcsUCCIFTI+Gl5AI5iuD9TnwKoLBcH0IIBNeSACYXAViyGfktfBg7oKr5SAMIXg/6wx6iI2CEIkcvKU5qKHqEIwoPK1BMKoNJCTN+Evb6r1hS0vIqQZ3n1+/F4gD7SGwYuz2Jnfbd2dIrioTr7TEW53eS381OIf8arPydNOfcWnxYA5B9sHqbds+dU1VIAih9sSpAnLJNhV8IeD+ZHfIEtnmQRyEvR3Z9XJBtj2QBtnD45HUUNlLgxYcBFxD40AA3AoASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASEAZAYAElBEASPA/+iI+eg+jlXoAAAAASUVORK5CYII=" alt="" />
根据余弦定理求出A的角度,之后求出所有角度,加起来是否为360,小于则扩大,大于则缩小边
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define pi acos(-1.0)
#define exp 1e-8
int main()
{
int t,n,i,j,flag,cas = ;
double a[];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
flag = ;
for(i = ; i<n; i++)
scanf("%lf",&a[i]);
a[n] = a[];
double l = ,r = ,mid;
for(i = ; i<=n; i++)
{
r = min(r,a[i]+a[i-]);
l = max(l,fabs(a[i]-a[i-]));
}
while(r-l>exp)
{
mid = (l+r)/;
double s,sum=;
for(i = ; i<=n; i++)
{
s = (a[i]*a[i]+a[i-]*a[i-]-mid*mid)/(2.0*a[i]*a[i-]);
sum+=acos(s);
}
if(fabs(sum-*pi)<exp)
{
flag = ;
break;
}
else if(sum>*pi)
r = mid;
else
l = mid;
}
printf("Case %d: ",cas++);
if(flag)
printf("%.3f\n",mid);
else
printf("impossible\n");
} return ;
}