Submission #653849

#	Time	Username	Problem	Language	Result	Execution time	Memory
653849		haojiandan	Fences (JOI18_fences)	C++14	100 / 100	13 ms	684 KiB

fences

// wygzgyw
#include <bits/stdc++.h>
using namespace std;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
	if (t<0) { putchar('-'); write(-t); return; }
	if (t>9) write(t/10);
	putchar('0'+t%10);
}
template <typename T> void writeln(T t) { write(t); puts(""); }
#define MP make_pair
const double PIE=acos(-1.0);
const int maxn=220;
const double eps=1e-5;
int n; double S;
struct node {
	double x,y;
	void get() { read(x),read(y); }
	friend node operator + (node A,node B) { return (node){A.x+B.x,A.y+B.y}; }
	friend node operator - (node A,node B) { return (node){A.x-B.x,A.y-B.y}; }
	friend double operator * (node A,node B) { return A.x*B.x+A.y*B.y; }
	friend double operator ^ (node A,node B) { return A.x*B.y-A.y*B.x; }
	friend node operator * (double a,node b) { return (node){b.x*a,b.y*a}; }
	friend node operator * (node b,double a) { return (node){b.x*a,b.y*a}; }
};
struct seg {
	node a,b;
	double len() { node c=b-a; return c.x*c.x+c.y*c.y; }
	node query(node c) {
		if (fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps) return a;
		node delta=b-a;
		double lamda=(delta*(c-a))/(delta*delta);
		if (lamda<0) lamda=0;
		if (lamda>1) lamda=1;
		return a+lamda*delta;
	}
} d[maxn],line,s[4];
double dis[maxn][maxn];
int Query(node a,seg b) {
	double tmp=(a-b.a)^(a-b.b);
	if (tmp>eps) return 1;
	if (tmp<eps) return 2;
	return 0;
}
bool check(seg A) {
	node a=A.a,b=A.b;
	if (min(a.x,b.x)>S-eps) return 1;
	if (max(a.x,b.x)<-S+eps) return 1;
	if (min(a.y,b.y)>S-eps) return 1;
	if (max(a.y,b.y)<-S+eps) return 1;/*
	if (a.x>b.x) swap(a,b);
	node delta=b-a;
	if (a.x<S&&S<b.x) {
		node c=a+delta*((S-a.x)/(b.x-a.x));
		if (-S<c.y&&c.y<S) return 0;
	}
	if (a.x<-S&&-S<b.x) {
		node c=a+delta*((-S-a.x)/(b.x-a.x));
		if (-S<c.y&&c.y<S) return 0;
	}
	if (a.y>b.y) swap(a,b);
	delta=b-a;
	if (a.y<S&&S<b.y) {
		node c=a+delta*((S-a.y)/(b.y-a.y));
		if (-S<c.x&&c.x<S) return 0;
	}
	if (a.y<-S&&-S<b.y) {
		node c=a+delta*((-S-a.y)/(b.y-a.y));
		if (-S<c.x&&c.x<S) return 0;
	}
	return 1;*/
	int res=0;
	res|=Query(d[n].a,A);
	res|=Query(d[n-1].a,A);
	res|=Query(d[n-2].a,A);
	res|=Query(d[n-3].a,A);
	return res!=3;
}
int Query(node a,node b) {
	double tmp=(a.x*b.y-a.y*b.x);
	if (tmp<eps) return 1;
	if (tmp>eps) return 2;
	return 0;
}
bool query(seg A) {
	node a=A.a,b=A.b;
	if ((Query(a,line.b)|Query(b,line.b))!=3) return 0;
	double k2=line.b.y/line.b.x;
	if (fabs(a.x-b.x)<eps) return min(0.0,line.b.x)<=a.x&&a.x<=max(0.0,line.b.x)&&min(0.0,line.b.y)<=a.x*k2&&a.x*k2<=max(0.0,line.b.y);
	double k=(b.y-a.y)/(b.x-a.x);
	if (fabs(k-k2)<eps) assert(0);
	double B=b.y-k*b.x;
	double x=B/(k2-k);
	return min(0.0,line.b.x)<=x&&x<=max(0.0,line.b.x);
}
int main() {
	//freopen("1.txt","r",stdin);
	read(n); read(S);
	for (int i=1;i<=n;i++) d[i].a.get(),d[i].b.get();
	d[++n]=(seg){(node){-S,-S},(node){-S,-S}};
	d[++n]=(seg){(node){-S,S},(node){-S,S}};
	d[++n]=(seg){(node){S,S},(node){S,S}};
	d[++n]=(seg){(node){S,-S},(node){S,-S}};
	
	double alpha=PIE*(rand()%200)*0.01;
	double T=1e4;
	line.a.x=line.a.y=0;
	line.b=(node){T*cos(alpha),T*sin(alpha)};
	//printf("%.5lf %.5lf\n",line.b.x,line.b.y);
	for (int i=1;i<=n*2;i++) for (int j=1;j<=n*2;j++) dis[i][j]=(i==j?0:1e9);
	for (int i=1;i<=n;i++) for (int j=i+1;j<=n;j++) {
		
		s[0]=(seg){d[i].a,d[j].query(d[i].a)};
		s[1]=(seg){d[i].b,d[j].query(d[i].b)};
		s[2]=(seg){d[j].a,d[i].query(d[j].a)};
		s[3]=(seg){d[j].b,d[i].query(d[j].b)};
		int k=0; for (int v=1;v<4;v++) if (s[k].len()>s[v].len()) k=v;
		if (!check(s[k])) continue;
		bool res=query(s[k]);
		if (k==0) res^=query((seg){d[j].a,s[0].b});
		if (k==1) res^=query(d[i])^query((seg){d[j].a,s[1].b});
		if (k==2) res^=query((seg){d[i].a,s[2].b});
		if (k==3) res^=query(d[j])^query((seg){d[i].a,s[3].b});
		if (res) dis[i][j+n]=dis[i+n][j]=dis[j+n][i]=dis[j][i+n]=sqrt(s[k].len());
		else dis[i][j]=dis[j][i]=dis[i+n][j+n]=dis[j+n][i+n]=sqrt(s[k].len());
	//	printf("%d %d %.5lf %d, %.5lf %.5lf\n",i,j,sqrt(s[k].len()),res,s[k].b.x,s[k].b.y);
	}
	for (int k=1;k<=n*2;k++) for (int i=1;i<=n*2;i++) for (int j=1;j<=n*2;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	double ans=1e9;
	for (int i=1;i<=n;i++) ans=min(ans,dis[i][i+n]);
	printf("%.5lf\n",ans);
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 33 / 33
• Subtask 3: 49 / 49