ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1215. Exactness of Projectile Hit

I have WA 21. Can you help me?
Posted by Denis 28 Nov 2007 02:28
Here's my code:

#include <fstream>
#include <stdio.h>
#include <cmath>
using namespace std;

long double eps = 1e-5;

double min (double a, double b)
{
    if (b-a > eps)
    {
        return a;
    }
    return b;
}

int n;
double x, y;
double arr[1110][2] = {0};

double dist (double x1, double y1, double x2, double y2)
{
    double sc1, sc2;
    double d1, d2, d;
    d1 = (x-x1)*(x-x1) + (y-y1)*(y-y1);
    d1 = sqrt (d1);
    d2 = (x-x2)*(x-x2) + (y-y2)*(y-y2);
    d2 = sqrt (d2);
    sc1 = (x-x1)*(x2-x1) + (y-y1)*(y2-y1);
    sc2 = (x-x2)*(x1-x2) + (y-y2)*(y1-y2);
    d = min (d1, d2);
    if (sc1 >= 0 && sc2 >= 0)
    {
        d1 = (x-x1)*(y2-y1) - (x2-x1)*(y-y1);
        d2 = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
        d2 = sqrt (d2);
        if (d2 > eps)
        {
            d1 /= d2;
            d1 = fabs (d1);
            if (d1 != 0)
            {
                d = min (d, d1);
            }
        }
    }
    return d;
}

int main ()
{
    //freopen ("a.in", "r", stdin);
    //freopen ("a.out", "w", stdout);
    int i, j;
    scanf ("%lf%lf%d", &x, &y, &n);
    for (i = 0; i < n; ++i)
    {
        scanf ("%lf%lf", &arr[i][0], &arr[i][1]);
    }
    double d = dist (arr[0][0], arr[0][1], arr[1][0], arr[1][1]);
    double d1;
    double angle = 0;
    double sn;
    double x1 = arr[0][0], x2 = arr[1][0], y1 = arr[0][1], y2 = arr[1][1];
    sn = (x1-x)*(y2-y) - (x2-x)*(y1-y);
    d1 = sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y))*sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y));
    sn /= d1;
    angle += asin (sn);
    for (i = 1; i < n; ++i)
    {
        j = (i+1)%n;
        x1 = arr[i][0], x2 = arr[j][0], y1 = arr[i][1], y2 = arr[j][1];
        sn = (x1-x)*(y2-y) - (x2-x)*(y1-y);
        d1 = sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y))*sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y));
        sn /= d1;
        angle += asin (sn);
        d1 = dist (arr[i][0], arr[i][1], arr[j][0], arr[j][1]);
        d = min (d, d1);
    }
    if (angle > 2.0)
    {
        printf ("0.000\n");
        return 0;
    }
    d *= 2.0;
    printf ("%.3lf\n", d);
    return 0;
}
Re: I have WA 21. Can you help me?
Posted by Mihran Hovsepyan {2 kurs of <RAU>} 27 Jul 2008 01:07
I have same problem.
I got WA21
please help me

# include <iostream.h>
# include <stdio.h>
# include <math.h>
int main ()
{
    int i,n,h1,h2,h3;
    double s1=0,s2=0,x,y,otv,min;
    double dx[100],dy[100];
    cin>>x>>y>>n;
    cin>>dx[0]>>dy[0]>>dx[1]>>dy[1];
    s2=fabs(0.5*((dx[0]-x)*(dy[1]-y)-(dx[1]-x)*(dy[0]-y)));
    for(i=2;i<n;i++)
    {
        cin>>dx[i]>>dy[i];
        s1+=fabs(0.5*((dx[i-1]-dx[0])*(dy[i]-dy[0])-(dx[i]-dx[0])*(dy[i-1]-dy[0])));
        s2+=fabs(0.5*((dx[i-1]-x)*(dy[i]-y)-(dx[i]-x)*(dy[i-1]-y)));
    }
    s2+=fabs(0.5*((dx[0]-x)*(dy[n-1]-y)-(dx[n-1]-x)*(dy[0]-y)));
    if(fabs(s1-s2)<=0.000000001)
    {
        cout<<"0.000";
        return 0;
    }
    else
    {
        min=sqrt((x-dx[0])*(x-dx[0])+(y-dy[0])*(y-dy[0]));
        h1=n-1;h2=0;h3=1;
        for(i=1;i<n;i++)
        {
            if(min>sqrt((x-dx[i])*(x-dx[i])+(y-dy[i])*(y-dy[i])))
            {
                min=sqrt((x-dx[i])*(x-dx[i])+(y-dy[i])*(y-dy[i]));
                h2=i;h1=i-1;h3=(i+1)%n;
            }
        }
        otv=min;
        double d1=fabs((x-dx[h2])*(dy[h1]-dy[h2])-(y-dy[h2])*(dx[h1]-dx[h2]))/sqrt((dy[h1]-dy[h2])*(dy[h1]-dy[h2])+(dx[h1]-dx[h2])*(dx[h1]-dx[h2]));
        double d2=fabs((x-dx[h2])*(dy[h3]-dy[h2])-(y-dy[h2])*(dx[h3]-dx[h2]))/sqrt((dy[h3]-dy[h2])*(dy[h3]-dy[h2])+(dx[h3]-dx[h2])*(dx[h3]-dx[h2]));
        if(((x-dx[h2])*(dx[h1]-dx[h2])+(y-dy[h2])*(dy[h1]-dy[h2]))+0.000000001>=0)
            if(d1<otv+0.00000001)
                otv=d1;
        if(((x-dx[h2])*(dx[h3]-dx[h2])+(y-dy[h2])*(dy[h3]-dy[h2]))+0.000000001>=0)
            if(d2<otv+0.00000001)
                otv=d2;
        printf("%.3lf",(2*otv));
    }
    return 0;
}
Re: I have WA 21. Can you help me?
Posted by ErOPb|4[USU] 8 Aug 2008 00:42
I also got WA#21 and don't know where is mistake in my code:
program z1215;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var px,py,n,i,nom,nom1,nom2:integer;
a:array [1..100,1..2] of integer;
r1,ab,bc,ac:real;
m:boolean;

function dlina (ab,bc,ac:real):real;
var p:real;
begin
if bc*bc+ab*ab-ac*ac<=0 then begin dlina :=bc; exit; end;
if ac*ac+ab*ab-ab*ab<=0 then begin dlina:= ac; exit; end;
p:=(ab+bc+ac)/2;
dlina:=(2*sqrt(p*(p-ac)*(p-bc)*(p-ab)))/ab;
end;
function func (x1,y1,x2,y2,xt1,yt1,xt2,yt2:integer):boolean;
var k1,k2,b1,b2,xp,yp:real;
k:integer;
m:boolean;
begin
m:=false;
 k:=0;
 if (x2-x1)<>0 then
 begin
  k1:= (y2-y1)/(x2-x1);
  b1:= y1-k1*x1;
 end
 else k:=1;
 if (xt2-xt1)<>0 then
 begin
  k2:= (yt2-yt1)/(xt2-xt1);
  b2:= yt1-k2*xt1;
 end
 else k:=k+10;
 if (k1<>k2) and (k=0) then
 xp:= (b2-b1)/(k1-k2);
 if k=1 then xp:=x1;
 if ((k1<>k2) or (k=1)) and ((xp-xt1)*(xp-xt2)>=0) and ((k=0) or (k=1))
 then m:= true;
 if (k1=k2) and (k=0) then m:= true;
 if k=11 then m:=true;
 if k=10 then
 begin
  yp:=k1*xt1+b1;
  if (yp-yt1)*(yp-yt2)>=0 then m:=true;
  end;
  func:=m;
 end;

begin
readln (px,py,n);
for i:=1 to n do
readln (a[i,1],a[i,2]);
for i:=1 to n-2 do
begin
m:=func(a[i,1],a[i,2],a[i+1,1],a[i+1,2],a[i+2,1],a[i+2,2],px,py);
if not m then break;
end;
if m then m:=func(a[n-1,1],a[n-1,2],a[n,1],a[n,2],a[1,1],a[1,2],px,py);
if m then m:=func(a[n,1],a[n,2],a[1,1],a[1,2],a[2,1],a[2,2],px,py);
if m then begin writeln ('0.000'); exit; end;
r1:=sqrt(sqr(px-a[1,1])+sqr(py-a[1,2]));
nom:=1;
for i:=2 to n do
if sqrt(sqr(px-a[i,1])+sqr(py-a[i,2]))<r1 then
begin
r1:=sqrt(sqr(px-a[i,1])+sqr(py-a[i,2]));
nom:=i;
end;
if nom>1 then nom1:=nom-1 else nom1:=n;
if nom<n then nom2:=nom+1 else nom2:=1;
if sqrt(sqr(px-a[nom2,1])+sqr(py-a[nom2,2]))<sqrt(sqr(px-a[nom1,1])+sqr(py-a[nom1,2])) then nom1:=nom2;
ab:=sqrt(sqr(a[nom,1]-a[nom1,1])+sqr (a[nom,2]-a[nom1,2]));
bc:=sqrt(sqr(a[nom,1]-px)+sqr (a[nom,2]-py));
ac:=sqrt(sqr(a[nom1,1]-px)+sqr (a[nom1,2]-py));
writeln ( 2*dlina(ab,bc,ac):1:3);
end.
Re: I have WA 21. Can you help me?
Posted by ErOPb|4[USU] 8 Aug 2008 20:51
I find the mistake, I have AC now.
Try this test:
0 0 3
100 1
0 2
-100 1
Correct answere is 2.000