ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1215. Точность попадания снаряда

I have WA 21. Can you help me?
Послано Denis 28 ноя 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?
Послано Mihran Hovsepyan {2 kurs of <RAU>} 27 июл 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?
Послано ErOPb|4[USU] 8 авг 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?
Послано ErOPb|4[USU] 8 авг 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