OJ Board

Code: Select all

program Project3;

{$APPTYPE CONSOLE}

uses
  SysUtils, Math;

const
  eps = 1e-5;

function distance (const x1,y1,x2,y2: extended): extended;
var
  a,b,t: extended;
begin
  a := sqr (x1-x2);
  b := sqr (y1-y2);
  t := a + b;
  t := sqrt (t);
  distance := t
end;

function distanceToLineSegment (const x,y,x1,y1,x2,y2: extended): extended;
var
  a,b,c,t: extended;
  aa,bb,cc: extended;
begin
  a := y2 - y1;
  b := x1 - x2;
  c := -abs(-x1*a - y1*b);
  t := sqrt (sqr(a)+sqr(b));

  if abs(a*x + b*y +c)<eps then
  begin
    if (x>=min(x1,x2)-eps) and (x<=max(x1,x2)+eps) and (y>=min(y1,y2)-eps) and (y<=max(y1,y2)+eps) then
      distanceToLineSegment := 0
    else
      distanceToLineSegment := maxint
  end
  else
  begin
    aa := sqr(distance (x,y,x1,y1));
    bb := sqr(distance (x,y,x2,y2));
    cc := sqr(distance (x1,y1,x2,y2));
    if (aa>bb+cc) or (bb>aa+cc) then
      distanceToLineSegment := min (aa,bb)
    else
      distanceToLineSegment := abs( (a*x + b*y + c)/t )
  end;
end;

var
  x1,y1,x2,y2,r: extended;
  a,b,c: extended;
  d: extended;
  d1,d2: extended;
  ci,cn: integer;
  ax1,ay1,ax2,ay2: extended;
  alpha,beta1,beta2,beta: extended;
  x11,y11,x12,y12,x21,y21,x22,y22: extended;
  a1,a2,a3,a4: extended;
  di: extended;

begin

  readln (cn);

  for ci := 0 to cn - 1 do
  begin
    readln (x1,y1,x2,y2,r);

    if (x1=x2) and (y1=y2) then
    begin
      writeln (0.0:0:3);
      continue
    end;


   { transform (x1,y1);
    transform (x2,y2);}


    d := distanceToLineSegment (0,0,x1,y1,x2,y2);

    if d>r-eps then
    begin
      writeln (distance(x1,y1,x2,y2):0:3);
      continue
    end;

    d := sqrt (sqr(x1) + sqr(y1));
    alpha := arcsin (r/d);
    alpha := pi/2.0 - alpha;

    beta := arctan2 (y1,x1);
    while beta<0 do
      beta := beta + 2*pi;
    beta1 := beta + alpha;
    beta2 := beta - alpha;

{    if abs(beta1)<eps then
      beta1 := 0;
    if abs(beta2)<eps then
      beta2 := 0;    }

    x11 := r*cos (beta1);
    y11 := r*sin (beta1);
    x12 := r*cos (beta2);
    y12 := r*sin (beta2);

    d := sqrt (sqr(x2) + sqr(y2));
    alpha := arcsin (r/d);
    alpha := pi/2.0 - alpha;

    beta := arctan2 (y2,x2);
    beta1 := beta + alpha;
    beta2 := beta - alpha;

    x21 := r*cos (beta1);
    y21 := r*sin (beta1);
    x22 := r*cos (beta2);
    y22 := r*sin (beta2);
    
    a1 := arctan2 (y11,x11);
    a2 := arctan2 (y12,x12);
    a3 := arctan2 (y21,x21);
    a4 := arctan2 (y22,x22);

    alpha := min ( min(abs(a1-a3),abs(a1-a4)) , min(abs(a2-a3),abs(a2-a4)) );

    d1 := alpha*r;

    d2 :=      min (distance (x1,y1,x11,y11), distance (x1,y1,x12,y12));
    d2 := d2 + min (distance (x2,y2,x21,y21), distance (x2,y2,x22,y22));
    d := d1 + d2;

    writeln (d:0:3)

  end;


end.

Code: Select all

#include<iostream>
#include<cmath>
#include<iomanip>

using namespace std;

double panjang(double x1, double y1, double x2, double y2);
double sudut(double a, double c);
void DistanceFromLine(double ax, double ay , double bx, double by );

double distanceLine, distanceSegment;

int main()
{
    double x1, y1, x2, y2, r, L1, L2, L3, A, B, C, c, busur, hasil;
    int N, i;
    
    cin>>N;
    for(i=0; i<N; i++)
    {
        cout<<fixed<<showpoint<<setprecision(3);
        cin>>x1>>y1>>x2>>y2>>r;
        L1=panjang(x1, y1, 0, 0);
        L2=panjang(x2, y2, 0, 0);
        L3=panjang(x1, y1, x2, y2);
        
        DistanceFromLine(x1,y1,x2,y2);
        if(distanceSegment>=r || L3==0)
           hasil=L3;
        else
        {
        A=sudut(r, L1);
        B=sudut(r, L2);
        C=acos((L3*L3-L2*L2-L1*L1)/(-2*L2*L1));
        c=C-A-B;
        busur=c*r;
        hasil=busur+sqrt(L1*L1-r*r)+sqrt(L2*L2-r*r);
        }
        cout<<hasil<<endl;
    }
    return 0;    
}

double panjang(double x1, double y1, double x2, double y2)
{
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
}

double sudut(double a, double c)
{
    return acos(a/c);    
}

void DistanceFromLine(double ax, double ay ,  double bx, double by)
{
        int cx=0;
        int cy=0;
        double r_numerator = (cx-ax)*(bx-ax) + (cy-ay)*(by-ay);
        double r_denomenator = (bx-ax)*(bx-ax) + (by-ay)*(by-ay);
        double r = r_numerator / r_denomenator;

        double px = ax + r*(bx-ax);
        double py = ay + r*(by-ay);

        double s =  ((ay-cy)*(bx-ax)-(ax-cx)*(by-ay) ) / r_denomenator;

        distanceLine = fabs(s)*sqrt(r_denomenator);

	double xx = px;
	double yy = py;

	if ( (r >= 0) && (r <= 1) )
	{
		distanceSegment = distanceLine;
	}
	else
	{

		double dist1 = (cx-ax)*(cx-ax) + (cy-ay)*(cy-ay);
		double dist2 = (cx-bx)*(cx-bx) + (cy-by)*(cy-by);
		if (dist1 < dist2)
		{
			xx = ax;
			yy = ay;
			distanceSegment = sqrt(dist1);
		}
		else
		{
			xx = bx;
			yy = by;
			distanceSegment = sqrt(dist2);
		}


	}
	
}

Code: Select all

//Rope Crisis in Ropeland!
/* @JUDGE_ID: 00000 10180 C++ */
//Técnicas Utilizadas: --
#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;

#define PI 3.141592653589793
#define _inline(f...) f() __attribute__((always_inline)); f
const double EPS = 1e-7;

_inline(int cmp)(double x, double y = 0, double tol = EPS) {
   return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
}

struct point{
   double x,y;
   point(double x=0.0, double y=0.0):x(x), y(y){}
};

struct line{
   double a;
   double b;
   double c;
};

double dist(point p1, point p2){
   return sqrt(pow(p2.x-p1.x,2.0)+pow(p2.y-p1.y,2.0));
}

void points_to_line(point p1, point p2, line *l){
   if (p1.x==p2.x) {
      l->a=1.0;
      l->b=0.0;
      l->c=-p1.x;
   }else{
      l->b=1.0;
      l->a=-(p1.y-p2.y)/(p1.x-p2.x);
      l->c=-(l->a*p1.x)-(l->b*p1.y);
   }
}

void point_and_slope_to_line(point p, double m, line *l){
   l->a=-m;
   l->b=1.0;
   l->c=-((l->a*p.x)+(l->b*p.y));
}

void intersection_point(line l1, line l2, point *p){
   p->x=(l2.b*l1.c-l1.b*l2.c)/(l2.a*l1.b-l1.a*l2.b);
   if (fabs(l1.b)>EPS) /* test for vertical line */
      p->y=-(l1.a*(p->x)+l1.c)/l1.b;
   else
      p->y=-(l2.a*(p->x)+l2.c)/l2.b;
}

void closest_point(point p_in, line l, point *p_c){
   line perp; /* perpendicular to l through (x,y) */
   if (fabs(l.b)<=EPS) { /* vertical line */
      p_c->x=-(l.c);
      p_c->y=p_in.y;
   return;
   }
   if (fabs(l.a)<=EPS) { /* horizontal line */
      p_c->x=p_in.x;
      p_c->y=-(l.c);
   return;
   }
   point_and_slope_to_line(p_in,1.0/l.a,&perp); /* normal case */
   intersection_point(l,perp,p_c);   
}

bool point_in_box(point p1, point p2, point pt){
   double min_x=min(p1.x,p2.x);
   double max_x=max(p1.x,p2.x);
   double min_y=min(p1.y,p2.y);
   double max_y=max(p1.y,p2.y);
   if(cmp(pt.x,min_x)>=0 && cmp(pt.x,max_x)<=0 && cmp(pt.y,min_y)>=0 && cmp(pt.y,max_y)<=0)
      return true;
   return false;
}

bool isPerpendicular(point p, point t){
	line l1, l2;
	points_to_line(p,t,&l1);
	points_to_line(point(0.0,0.0),t,&l2);	
    if (cmp(l1.a,0.0)==0)
		return(cmp(l2.b,0.0)==0);
	else if (cmp(l2.a,0.0)==0)
		return(cmp(l1.b,0.0)==0);
	else
		return (cmp(l1.a,(-1.0/l2.a))==0);	
}

void tangentPoints(point p, double r, point &t1, point &t2){
	if(cmp(r*r-p.x*p.x-p.y*p.y,0.0)==0){
       t1=point(p.x,p.y);
       t2=point(p.x,p.y);
       return;
    }
    double a=(p.x*p.x+p.y*p.y);
	double b=-2.0*r*r*p.x;
	double c=r*r*r*r-p.y*p.y*r*r;
	double delta=b*b-4*a*c;
	double s1=(-b+sqrt(delta))/(2.0*a);
	double s2=(-b-sqrt(delta))/(2.0*a);
	t1=point(s1,sqrt(r*r-s1*s1));
    if (!isPerpendicular(p,t1))
		t1.y*=-1.0;	
	t2=point(s2,sqrt(r*r-s2*s2));
	if (!isPerpendicular(p,t2))
		t2.y*=-1.0;
}

double getArch(point p1, point p2, double r){
   double a=dist(p1,p2);
   double teta=acos((pow(a,2.0)-pow(r,2.0)-pow(r,2.0))/(-2.0*r*r));   
   return (r*teta);
}

int main(){ 
    int n;   
    point p1, p2, pc, t1_p1, t2_p1, t1_p2, t2_p2;    
    double r,arch1,arch2,min_arch;
    line l;
    cin>>n;
    for(int i=0; i<n; i++){       
       cin>>p1.x>>p1.y>>p2.x>>p2.y>>r;
       if(cmp(dist(p1,p2),0.0)==0){
          cout<<"0.000\n";
          continue;
       }
       points_to_line(p1,p2,&l);
       closest_point(point(0.0,0.0), l, &pc);       
       if(cmp(dist(point(0.0,0.0),pc),r)<0 && point_in_box(p1,p2,pc)){          
          tangentPoints(p1,r,t1_p1,t2_p1);          
          tangentPoints(p2,r,t1_p2,t2_p2);
          if(cmp(dist(t1_p1,t1_p2),dist(t1_p1,t2_p2))<=0)
             arch1=getArch(t1_p1,t1_p2,r);
          else
             arch1=getArch(t1_p1,t2_p2,r);
          if(cmp(dist(t2_p1,t1_p2),dist(t2_p1,t2_p2))<=0)
             arch2=getArch(t2_p1,t1_p2,r);
          else
             arch2=getArch(t2_p1,t2_p2,r);
          min_arch=min(arch1,arch2);
          printf("%4.3f\n",dist(p1,t1_p1)+min_arch+dist(p2,t1_p2));
       }else
          printf("%4.3f\n",dist(p1,p2));                                                  
    }
    return 0;
}

Code: Select all

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long Long;
struct Pt
{
    double x,y;
    Pt(double a,double b)
    {
        x = a; y = b;
    }
    double operator *(const Pt &P)const
    {
        return x*P.x + y*P.y;
    }
    Pt operator -(const Pt &P)const
    {
        return Pt(x-P.x, y-P.y);
    }
};
typedef Pt Point;
double sdist(Point A, Point B)
{
    return (A-B)*(A-B);
}

double length(Point A,Point B,double R)
{
    Point C(0,0);
    double dAC = A.x*A.x + A.y*A.y;
    double dBC = B.x*B.x + B.y*B.y;
    double dAB = sdist(A,B);
    if(R < 1e9)return sqrt(dAB);
    double angl = acos((dBC+dAC-dAB)/(2.0*sqrt(dAC)*sqrt(dBC)));
    double T1 = acos(R/sqrt(dAC));
    double T2 = acos(R/sqrt(dBC));
    angl -= T1 + T2;
    if(angl < 1e-9)return sqrt(dAB);
    if(dAC - R*R < 0 && dBC - R*R < 0)return angl*R;
    if(dAC - R*R < 0)return sqrt(dBC - R*R) + angl*R;
    if(dBC - R*R < 0)return sqrt(dAC - R*R) + angl*R;
    return sqrt(dAC - R*R) + sqrt(dBC - R*R) + angl*R;
}

int main(int argc, char** argv)
{
    int TC;
    freopen("in.txt","r",stdin);
    cin>>TC;
    for(int tc = 1; tc<=TC; ++tc)
    {
        double X1,Y1,X2,Y2,R;
        scanf("%lf %lf %lf %lf %lf",&X1,&Y1,&X2,&Y2,&R);
        printf("%0.3lf\n",length(Point(X1,Y1),Point(X2,Y2),R));
    }
    return 0;
}





/*
 * File:   10180.cpp
 * Author: Soporte Tecnico
 *
 * Created on 20 de abril de 2011, 07:00 AM
 */

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int ch(double a, double b)
{
    if((a > 0 && b < 0) || (a < 0 && b > 0))return 1;
    else return 2;
}

int main()
{
    int t;
    double x1, y1, x2, y2, r, d, d1, d2, t1, t2, pl, m, rl, theta, arc;
    scanf("%d", &t);
    while(t--){
        scanf("%lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &r);
        if(x1 == x2){
            if(fabs(x1) <= r && fabs(y1) >= r && fabs(y2) >= r && ch(y1, y2) == 2)pl = fabs(y1);
            else pl = fabs(x1);
        }
        else if(y1 == y2){
            if(fabs(y1) <= r && fabs(x1) >= r && fabs(x2) >= r && ch(x1, x2) == 2)pl = fabs(x1);
            else pl = fabs(y1);
        }
        else{
            m = (y2 - y1) / (x2 - x1);
            pl = fabs((- m*x1 + y1) / sqrt(pow(m, 2) + 1));
        }
        if(pl >= r)rl = sqrt(pow((x1-x2), 2) + pow((y1-y2), 2));
        else{
            t1 = sqrt(pow(x1, 2) + pow(y1, 2) - pow(r, 2));
            t2 = sqrt(pow(x2, 2) + pow(y2, 2) - pow(r, 2));
            d1 = sqrt(pow(x1, 2) + pow(y1, 2));
            d2 = sqrt(pow(x2, 2) + pow(y2, 2));
            d = sqrt(pow((x1-x2), 2) + pow((y1-y2), 2));
            theta = (acos((pow(d1, 2) + pow(d2, 2) - pow(d, 2)) / (2*d1*d2))) - ((acos((pow(d1, 2) + pow(r, 2) - pow(t1, 2)) / (2*d1*r))) + (acos((pow(d2, 2) + pow(r, 2) - pow(t2, 2)) / (2*r*d2))));
            arc = theta * r;
            rl = t1 + arc + t2;
        }
        printf("%.3lf\n", rl);
    }
    return 0;
}