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
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details