General

# Author Problem Lang Verdict Time Memory Sent Judged
50277010 Practice:
lalaxu
696F - 21 GNU C++11 Accepted 46 ms 27728 KB 2019-02-21 13:39:50 2019-02-21 13:39:50

→ Source
#include<iostream>
#include<cmath>
using namespace std;
const int N=1005;
struct Node
{
double x,y;
Node operator + (Node A) {return (Node){x+A.x,y+A.y};}
Node operator - (Node A) {return (Node){x-A.x,y-A.y};}
Node operator ^ (double t) {return (Node){x*t,y*t};}
double operator * (Node A) {return x*A.y-y*A.x;}
double dis() {return sqrt(x*x+y*y);}
}O[N][N],t[N],E[N];
int n,yes[N][N];
double Or[N][N];
Node Getcrs(Node a1,Node a2,Node b1,Node b2)
{
Node a=a2-a1,b=b2-b1,c=b1-a1;
double t=(b*c)/(b*a);
return a1+(a^t);
}
double disline(int i,Node A) {return abs(E[i]*(A-t[i])/E[i].dis());}
int ch(int R) {return R%n?R%n:n;}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%lf%lf",&t[i].x,&t[i].y);
for(int i=1;i<=2*n;i++) t[n+i]=t[i];
for(int i=1;i<=3*n;i++) E[i]=t[i+1]-t[i];
for(int L=1;L<=n;L++)
{
yes[L][L]=1;O[L][L]=t[L];
yes[L][ch(L+1)]=1;O[L][ch(L+1)]=t[L+1];
}
for(int L=1;L<=n;L++)
for(int R=L+2,nw=L;R==L||E[L]*E[R]>0;R++)
{
while(nw<R&&disline(L,t[nw+1])<disline(R,t[nw+1])) ++nw;
Node P1=Getcrs(t[L],t[L+1],t[R],t[R+1]);
Node e=t[R+1]-t[R];e=e^(1.0/e.dis());
Node P2=P1+(e^(t[L+1]-P1).dis());
Node P3=(t[L+1]+P2)^0.5;
Node P=Getcrs(P1,P3,t[nw],t[nw+1]);
yes[L][ch(R)]=1;O[L][ch(R)]=P;
Or[L][ch(R)]=max(disline(L,P),disline(R,P));
}
double r=1e7;Node o1,o2;
for(int L=1;L<=n;L++)
for(int R=L;R<=L+n;R++)
if(yes[L][ch(R)]&&yes[ch(R+1)][ch(L-1+n)])
{
double newr=max(Or[L][ch(R)],Or[ch(R+1)][ch(L-1+n)]);
if(newr<r) r=newr,o1=O[L][ch(R)],o2=O[ch(R+1)][ch(L-1+n)];
}
printf("%.10f\n%.10f %.10f\n%.10f %.10f\n",r,o1.x,o1.y,o2.x,o2.y);
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?