loj #2008. 「SCOI2015」小凸想跑步 #2008. 「SCOI2015」小凸想跑步
题目描述
小凸晚上喜欢到操场跑步，今天他跑完两圈之后，他玩起了这样一个游戏。
操场是个凸 n nn 边形，N NN 个顶点按照逆时针从 0∼n−1 0 sim n - 10∼n−1 编号。现在小凸随机站在操场中的某个位置，标记为 P PP 点。将 P PP 点与 n nn 个顶点各连一条边，形成 N NN 个三角形。如果这时 P PP 点，0 00 号点，1 11 号点形成的三角形的面积是 N NN 个三角形中最小的一个，小凸则认为这是一次正确站位。
现在小凸想知道他一次站位正确的概率是多少。
输入格式
第一行包含 1 11 个整数 n nn，表示操场的顶点数和游戏的次数。
接下来有 N NN 行，每行包含两个整数 Xi X_iXi、Yi Y_iYi 表示顶点的坐标。
输入保证按逆时针顺序输入点，所有点保证构成一个 n nn 多边形。所有点保证不存在三点共线。
输出格式
输出一个数，正确站位的概率，保留 4 44 位小数。
样例
样例输入
5
1 8
0 7
0 0
8 0
8 8样例输出
0.6316数据范围与提示
3≤N≤105,−109≤X,Y≤109 3 leq N leq 10 ^ 5, -10 ^ 9 leq X, Y leq 10 ^ 93≤N≤105,−109≤X,Y≤109
#include<iostream> #include<cstdio> #include<cstring> #define maxn 100010 #define eps 0.001 using namespace std; struct node{ double x,y; node(double a=0,double b=0):x(a),y(b){} node operator + (const node &c) {return node(x+c.x,y+c.y);} node operator - (const node &c) {return node(x-c.x,y-c.y);} double operator * (const node &c) {return x*c.y-y*c.x;} node operator / (const double c) {return node(x/c,y/c);} }p[maxn]; int n; double cnt1,cnt2,S; double abs(double x){return x>0?x:-x;} void check(double x,double y){ node point=node(x,y); double mn=1000;int k=-1;double sum=0; for(int i=0;i<n;i++){ node a=p[i],b=p[(i+1)%n]; double s=(a-point)*(b-point)*0.5; s=abs(s); if(s<mn)mn=s,k=i; sum+=s; } if(abs(sum-S)<=eps){ cnt1+=1; if(k==0)cnt2+=1; } } int main(){ scanf("%d",&n); double mxx=0,mnx=100,mxy=0,mny=100; for(int i=0;i<n;i++){ scanf("%lf%lf",&p[i].x,&p[i].y); mxx=max(mxx,p[i].x); mxy=max(mxy,p[i].y); mnx=min(mnx,p[i].x); mny=min(mny,p[i].y); } for(int i=0;i<n;i++) S+=(p[i]-p[0])*(p[i+1]-p[0]); S*=0.5; S=abs(S); for(double i=mnx;i<=mxx;i+=0.001) for(double j=mny;j<=mxy;j+=0.001) check(i,j); cnt2+=(n-3)*300;cnt1+=(n-3)*300; cnt2/=cnt1; printf("%.4lf",cnt2); return 0; }
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 200010 using namespace std; struct node{ long double x,y; node(){} node(long double a,long double b){x=a,y=b;} node operator + (const node &a) {return node(x+a.x,y+a.y);} node operator - (const node &a) {return node(x-a.x,y-a.y);} node operator * (const long double &a) {return node(x*a,y*a);} long double operator * (const node &a) {return x*a.y-y*a.x;} }p[maxn]; struct line{ node p,v; long double a; line(){} line(node x,node y){p=x,v=y,a=atan2(v.y,v.x);} }l[maxn]; int n,tot,h,t,q[maxn]; long double ans,sum; bool onleft(line a,node b){ return a.v*(b-a.p)>=0; } node getp(line a,line b){ node u=a.p-b.p; long double tmp=(b.v*u)/(a.v*b.v); return a.p+a.v*tmp; } bool cmp(line a,line b){ if(fabs(a.a-b.a)==0)return onleft(a,b.p); return a.a<b.a; } inline void work(){ sort(l+1,l+tot+1,cmp); int j=1; for(int i=2;i<=tot;i++) if(fabs(l[i].a-l[j].a)>0) l[++j]=l[i]; tot=j; h=1,t=2,q[1]=1,q[2]=2; for(int i=3;i<=tot;i++){ while(h<t&&onleft(l[i],getp(l[q[t-1]],l[q[t]])))t--; while(h<t&&onleft(l[i],getp(l[q[h+1]],l[q[h]])))h++; q[++t]=i; } while(h<t&&onleft(l[q[h]],getp(l[q[t-1]],l[q[t]])))t--; for(int i=h;i<t;i++) p[i]=getp(l[q[i]],l[q[i+1]]); p[t]=getp(l[q[t]],l[q[h]]); for(int i=h;i<t;i++)ans+=p[i]*(p[i+1]-p[i]); ans+=p[t]*(p[h]-p[t]); } int main(){ freopen("Cola.txt","r",stdin); scanf("%d",&n); for(int i=0;i<n;i++)cin>>p[i].x>>p[i].y; p[n]=p[0]; for(int i=0;i<n;i++){ l[++tot]=line(p[i+1],p[i]-p[i+1]); sum+=p[i]*(p[i+1]-p[i]); } for(int i=1;i<n;i++){ long double a=p[i+1].x-p[i].x-p[1].x+p[0].x; long double b=p[i+1].y-p[i].y-p[1].y+p[0].y; long double c=-(p[i]*(p[i+1]-p[i]))+(p[0]*(p[1]-p[0])); if(fabs(a)>0)l[++tot]=line(node(0,c/a),node(-a,-b)); else if(fabs(b)>0)l[++tot]=line(node(-c/b,0),node(0,-b)); } work(); printf("%.4lf",(double)fabs(ans/sum)); return 0; }