tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 1283

やらかしました。

手元とPKUでは正解なのにAOJではWAだったのはどうやら配列外参照のせいらしい。
C++は配列外処理のレスポンスが環境によってかわりすぎる。JavaみたいにすべてREにしてほしい。
(CFでC++の配列外処理はhackすることができない)

やってることは二分探索して直線出して交点求めて内外判定と距離を見ているだけですが、凸カットなんてものもあるらしいですね。幾何もっと精進します。

#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>
using namespace std;
double x[200];
double y[200];
double EPS=1e-9;
struct L{ // ax+by+c=0
	double a,b,c;
	L(){}
	L(double A,double B,double C){
		a=A;
		b=B;
		c=C;
	}
};
double Abs(double a){return max(a,-a);}
struct P{
	double x,y;
	P(){}
	P(double X,double Y){
		x=X;
		y=Y;
	}
};
P inter(L s,L t){
	double det=s.a*t.b-s.b*t.a;
	if(Abs(det)<EPS){
		return P(1000000009,1000000009);
	}
	return P((-t.b*s.c+s.b*t.c)/det,(-t.c*s.a+s.c*t.a)/det);
}
double dot(P a,P b){
	return a.x*b.x+a.y*b.y;
}
double cross(P a,P b){
	return a.x*b.y-a.y*b.x;
}
double norm(P a){
	return a.x*a.x+a.y*a.y;
}
int ccw(P a,P b,P c){
	b.x-=a.x;
	b.y-=a.y;
	c.x-=a.x;
	c.y-=a.y;
	if(cross(b,c)>0)return 1;
	if(cross(b,c)<0)return -1;
	if(dot(b,c)<0)return 2;
	if(norm(b)<norm(c))return -2;
	return 0;
}
double dist(L s,P t){ // 点と直線の距離
	return Abs(s.a*t.x+s.b*t.y+s.c)/sqrt(s.a*s.a+s.b*s.b);
}
L convLine(P s,P t){ // (x1,y1),(x2,y2)を通る直線の型変換
	double theta=atan2(t.y-s.y,t.x-s.x);
	double A=sin(theta);
	double B=-cos(theta);
	double C=-(s.x*A+s.y*B);
	return L(A,B,C);
}
L lines[200];
L poly[102];
P point[102];
int main(){
	int a;
	int n=0;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++){
			scanf("%lf%lf",x+i,y+i);
		}
		x[a]=x[0];
		y[a]=y[0];
		for(int i=0;i<=a;i++)point[i]=P(x[i],y[i]);
		for(int i=0;i<a;i++){
			poly[i]=convLine(point[i],point[i+1]);
		//	printf("%f %f %f\n",poly[i].a,poly[i].b,poly[i].c);
		}
		double left=0;
		double right=10000;
		for(int i=0;i<50;i++){
			double M=(left+right)/2;
			for(int j=0;j<a;j++){
				lines[j*2]=L(poly[j].a,poly[j].b,poly[j].c-M);
				lines[j*2+1]=L(poly[j].a,poly[j].b,poly[j].c+M);
			}
			vector<P> points;
			for(int j=0;j<2*a;j++){
				for(int k=j+1;k<2*a;k++){
					P val=inter(lines[j],lines[k]);
					if(Abs(val.x-1000000009)>EPS){
						points.push_back(val);
					}
				}
			}
			bool ok=false;
			for(int j=0;j<points.size();j++){
				bool OK=true;
				for(int k=0;k<a;k++){
					if(dist(poly[k],points[j])+EPS<M){
						OK=false;
						break;
					}
					if(ccw(point[k],points[j],point[k+1])!=-1)OK=false;
				}
				if(OK){
					ok=true;
					break;
				}
			}
			if(ok){
				left=M;
			}else right=M;
		}
		printf("%.8f\n",left);
		n++;
	}
	if(n>29)return 1;
	
}