## 12818 - Arc and Point

Moderator: Board moderators

invoker
New poster
Posts: 2
Joined: Tue Oct 21, 2014 8:43 am

### 12818 - Arc and Point

Code: Select all

``````#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <list>
#include <vector>
#include <ctime>
#define LL __int64
#define eps 1e-8
using namespace std;
double X0,X1,X2,X3,px,py,Y0,Y1,Y2,Y3,R;
int flag;
struct point
{
double x,y;
point (double x=0,double y=0):x(x),y(y){}
};
int dcmp(double x)
{
if (fabs(x)<eps) return 0;
else return x<0?-1:1;
}
double findy(double x)
{
double ans=0;
ans=sqrt(R-(x-X0)*(x-X0))+Y0;
return ans;
}
double dis(double x,double y,double xx,double yy)
{
return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
}
int sfun(point a,point b,point c)
{
int ans=(a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
if (ans>0) return 1;
if (ans<0) return -1;
if (ans==0) return 0;
}
point go(point v,point l,point r)
{
if (X0==v.x && Y0==v.y)
{
point p1,p2;
p1=point(l.y-v.y+v.x,l.x-v.x+v.y);
p2=point(l.y-v.y+v.x,v.x-l.x+v.y);
if (sfun(l,r,p1)==flag)
return p1;
else return p2;
}
else
{
double gg=dis(v.x,v.y,X0,Y0);
double gg1=sqrt(R);
l.x=X0+(v.x-X0)/gg*gg1;
l.y=Y0+(v.y-Y0)/gg*gg1;
//	point rr=point(X0,Y0);
//	if (sfun(rr,l,v)==0) cout<<"%%%"<<endl;
return l;
}
}
int main()
{
int cas=1;
//freopen("out.txt","w",stdout);
while (~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2,&X3,&Y3,&px,&py))
{
double k,k1,g,g1,z,z1,a,b,a1,b1;
k=2*(X1-X2);k1=2*(X1-X3);
g=2*(Y1-Y2);g1=2*(Y1-Y3);
z=Y1*Y1+X1*X1-X2*X2-Y2*Y2;
z1=Y1*Y1+X1*X1-X3*X3-Y3*Y3;
a=k/g;b=z/g;
a1=k1/g1;b1=z1/g1;
if (k==0)
{
Y0=z/g;
X0=(z1-g1*Y0)/k1;
}
else if (k1==0)
{
Y0=z1/g1;
X0=(z-g*Y0)/k;
}
else if (g==0)
{
X0=z/k;
Y0=(z1-k1*X0)/g1;
}
else if (g1==0)
{
X0=z1/k1;
Y0=(z-k*X0)/g;
}
else
{
X0=(b1-b)/(a1-a);
Y0=(z-k*X0)/g;
}
R=(X1-X0)*(X1-X0)+(Y1-Y0)*(Y1-Y0);
point l=point(X1,Y1);
point r=point(X3,Y3);
point zh=point(X2,Y2);
flag=sfun(l,r,zh);
double ans=0x3fffffff;
int w1=0,w2=0,w3=0;
w1=dis(X0,Y0,l.x,l.y);
w2=dis(X0,Y0,r.x,r.y);
w3=dis(X0,Y0,zh.x,zh.y);
double rr=sqrt(R);
//	cout<<w1<<w2<<w3<<endl;
//	if (w1-rr<=eps && w2-rr<=eps && w3-rr<=eps) cout<<"YES"<<endl;
while (dis(l.x,l.y,r.x,r.y)>eps)
{
point v=point((l.x+r.x)/2,(l.y+r.y)/2);
point mid=go(v,l,r);
double gl=dis(l.x,l.y,px,py);
double gr=dis(r.x,r.y,px,py);
if (gl>=gr)
{
if (ans-gr>eps)
ans=gr;
l.x=mid.x;
l.y=mid.y;
}
else
{
if (ans-gl>eps)
ans=gl;
r.x=mid.x;
r.y=mid.y;
}
}
printf("Case %d: %lf\n",cas++,ans);
}
return 0;
}``````
can't AC...why...
Last edited by brianfry713 on Tue Oct 21, 2014 9:51 pm, edited 2 times in total.

invoker
New poster
Posts: 2
Joined: Tue Oct 21, 2014 8:43 am

### Re: 12818 - Arc and Point

Code: Select all

``````#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <list>
#include <vector>
#include <ctime>
#define LL __int64
#define eps 1e-8
using namespace std;
double X0,X1,X2,X3,px,py,Y0,Y1,Y2,Y3,R;
int flag;
struct point
{
double x,y;
point (double x=0,double y=0):x(x),y(y){}
};
int dcmp(double x)
{
if (fabs(x)<eps) return 0;
else return x<0?-1:1;
}
double findy(double x)
{
double ans=0;
ans=sqrt(R-(x-X0)*(x-X0))+Y0;
return ans;
}
double dis(double x,double y,double xx,double yy)
{
return sqrt((xx-x)*(xx-x)+(yy-y)*(yy-y));
}
int sfun(point a,point b,point c)
{
point o2=point(b.x-a.x,b.y-a.y);
point o1=point(c.x-a.x,c.y-a.y);
int ans=(o1.x)*(o2.y)-(o1.y)*(o2.x);
if (ans>0) return 1;
if (ans<0) return -1;
if (ans==0) return 0;
}
double Min(double a,double b,double c)
{
if (a-b>eps)
a=b;
if (a-c>eps)
a=c;
return a;
}
int main()
{
int cas=1;
//freopen("out1.txt","w",stdout);
while (~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2,&X3,&Y3,&px,&py))
{
double k,k1,g,g1,z,z1,a,b,a1,b1;
k=2*(X1-X2);k1=2*(X1-X3);
g=2*(Y1-Y2);g1=2*(Y1-Y3);
z=Y1*Y1+X1*X1-X2*X2-Y2*Y2;
z1=Y1*Y1+X1*X1-X3*X3-Y3*Y3;
a=k/g;b=z/g;
a1=k1/g1;b1=z1/g1;
if (k==0)
{
Y0=z/g;
X0=(z1-g1*Y0)/k1;
}
else if (k1==0)
{
Y0=z1/g1;
X0=(z-g*Y0)/k;
}
else if (g==0)
{
X0=z/k;
Y0=(z1-k1*X0)/g1;
}
else if (g1==0)
{
X0=z1/k1;
Y0=(z-k*X0)/g;
}
else
{
X0=(b1-b)/(a1-a);
Y0=(z-k*X0)/g;
}
R=(X1-X0)*(X1-X0)+(Y1-Y0)*(Y1-Y0);
point l=point(X1,Y1);
point r=point(X3,Y3);
point zh=point(X2,Y2);
point xx=point(px,py);
point o=point(X0,Y0);
flag=sfun(l,r,zh);
int gg=sfun(l,r,xx);
int gg1=sfun(l,o,xx);
int gg2=sfun(o,r,xx);
double ans=0;
double q1,q2,q3;
if (gg==flag)
{
if (gg1==gg2)
{
q1=dis(xx.x,xx.y,X0,Y0);
//cout<<sqrt(R)<<" "<<q1<<endl;
if (q1-sqrt(R)>=0) q1-=sqrt(R);
}
else q1=0x3fffffff;
q2=dis(xx.x,xx.y,l.x,l.y);
q3=dis(xx.x,xx.y,r.x,r.y);
ans=Min(q1,q2,q3);
}
else
{
int gg3=sfun(r,l,xx);
if (gg1==gg2 && gg1==gg3)
{
q1=sqrt(R)-dis(xx.x,xx.y,X0,Y0);
q2=dis(xx.x,xx.y,l.x,l.y);
q3=dis(xx.x,xx.y,r.x,r.y);
ans=Min(q1,q2,q3);
}
else
{
double q1=dis(xx.x,xx.y,l.x,l.y);
double q2=dis(xx.x,xx.y,r.x,r.y);
if (q1-q2>=0) ans=q2;
else ans=q1;
}
}
printf("Case %d: %.3lf\n",cas++,ans);
}
return 0;
}``````
Last edited by brianfry713 on Tue Oct 21, 2014 7:41 pm, edited 1 time in total.