The test contents points entered clockwise, which doesn't respond the condition.
I succeed passing the test only after applied an algo, which is not sesitive to the order of points in polygone

Edited by author 29.04.2024 19:57

Edited by author 29.04.2024 19:57

Use int64_t :)

Edited by author 26.03.2009 23:03

Edited by author 26.03.2009 23:03

I got WA #4, but I think I got all special cases ok, so help please.

help plz...




#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

struct Point{
  int x,y;
  Point(int x=0,int y=0):x(x),y(y){}
  void Read(){ scanf("%d %d",&x,&y);}
  int operator ^ (Point o){ return x*o.y-o.x*y;}
  int operator * (Point o){ return x*o.x+y*o.y;}
  Point operator - (Point o){ return Point(x-o.x,y-o.y);}
}P[10000],buf;

double dis(double a,double b,double c,Point P){
  return (a*(double)P.x+b*(double)P.y+c)/(sqrt(a*a+b*b));
}

double dis(Point p,Point q){
     return sqrt((double)((q-p)*(q-p)));
}

int n;
int main(){
  buf.Read(); scanf("%d",&n);
  rep(i,n) P[i].Read(); P[n]=P[0]; P[n+1]=P[1];

  bool inCon=1;
  rep(i,n) {
    if( ((P[i+1]-P[i]) ^ (buf-P[i])) * ((P[i+2]-P[i+1]) ^ (buf-P[i+1])) <0 ){
      inCon=0; break;
    }
  }
  if(inCon) {printf("0.000"); return 0;}


  double ans=19970815.0;
  rep(i,n){
    Point N(P[i+1].y-P[i].y,P[i].x-P[i+1].x); // fa xiang
    double c=-(N*P[i]);
    double d= ((P[i]-P[i+1])*(buf-P[i+1])) * ((P[i+1]-P[i])*(buf-P[i])) >0
     ?dis(N.x,N.y,c,buf)
     : min(dis(P[i],buf),dis(P[i+1],buf));

    if(ans>d) ans=d;
  }



  printf("%.03lf",ans*2);
}

0 0 3
100 1
0 2
-100 1
Correct answere is 2.000

If you have WA7 then check up: the point is inside the polygon or not.

Ma prietenule! Ce mai faci? Vrei sa ma iubesti?

 var
  i,j,k,n,m,tot:longint;
  ans,x1,y1,x2,y2,d1,d2,d3,x,y,angle1,angle2,t,p1,p2:double;

 function min(xx,yy:double):double;
  begin
   if xx>yy then exit(yy);
   exit(xx);
  end;

 begin
  {assign(input,'1215.in');reset(input);}
  read(x,y,n);
  read(x1,y1);
  p1:=x1;
  p2:=y1;
  d1:=sqrt(sqr(x-x1)+sqr(y-y1));
  ans:=999999999;
  tot:=0;
  for i:=2 to n do
   begin
    read(x2,y2);
    if (x1<x)and(x2>=x)and((y1<y)or(y2<y))
     then
      inc(tot);
    d2:=sqrt(sqr(x-x2)+sqr(y-y2));
    d3:=sqrt(sqr(x1-x2)+sqr(y1-y2));
    angle1:=(d2*d2+d3*d3-d1*d1)/(2*d2*d3);
    angle2:=(d1*d1+d3*d3-d2*d2)/(2*d1*d3);
    if (angle1>=0)and(angle2>=0)
     then
      begin
       if x1=x2
        then
         t:=abs(x1-x)
        else
         t:=((y1-y2)/(x1-x2)*x-y+y1+(y2-y1)/(x1-x2)*x1)/(sqrt(sqr((y1-y2)/(x1-x2))+1));
       t:=abs(t);
       ans:=min(ans,t);
      end
     else
      begin
       t:=min(d1,d2);
       ans:=min(ans,t);
      end;
    d1:=d2;
    x1:=x2;
    y1:=y2;
   end;
  x2:=p1;
  y2:=p2;
  if (x1<x)and(x2>=x)and((y1<y)or(y2<y))
     then
      inc(tot);
    d2:=sqrt(sqr(x-x2)+sqr(y-y2));
    d3:=sqrt(sqr(x1-x2)+sqr(y1-y2));
    angle1:=(d2*d2+d3*d3-d1*d1)/(2*d2*d3);
    angle2:=(d1*d1+d3*d3-d2*d2)/(2*d1*d3);
    if (angle1>=0)and(angle2>=0)
     then
      begin
       if x1=x2
        then
         t:=abs(x1-x)
        else
         t:=((y1-y2)/(x1-x2)*x-y+y1+(y2-y1)/(x1-x2)*x1)/(sqrt(sqr((y1-y2)/(x1-x2))+1));
       t:=abs(t);
       ans:=min(ans,t);
      end
     else
      begin
       t:=min(d1,d2);
       ans:=min(ans,t);
      end;
  if odd(tot)
   then
    ans:=0;
  writeln(ans*2:0:3);
 end.

easy
simple binary search for r... Just a case with the point in target.

Can the projectile hit the target? If so, is the answer 0?

Any Hint?

Look here. It's my code!
Pz. find good tests for it!
//1215_SB
#include <iostream>
#include <cmath>
using namespace std;
#define eps 0.000001
struct Point{
// ....};
inline double triangle_S(Point& pa, Point& pb, Point& pc){
//calculates square of truiangle...
}
inline long double min_dist_to_line(Point& A, Point& B, Point& C)
{
    //here are a big and fat bug :)
    Point S;
    S.x = (B.x + A.x)/2.0;
    S.y = (B.y + A.y)/2.0;
    long double res = 0.0;
    long double a = C.dist(A);
    long double b = C.dist(B);
    long double d = A.dist(B);
    long double s = C.dist(S);

    if((s < a)&&(s < b))
    {
        res = sqrt(a*a - ((a*a - b*b + d*d)/(2.0*d))*((a*a - b*b + d*d)/(2.0*d)));
    }
    else
        res = (a > b) ? b : a;
    return res;

}
Point a[103];
int main()
{
    int n, i;
//getting the data
    double S_of_target = 0.0;
    for (int i = 1; i <= n; i++)
    {
        S_of_target += triangle_S(Dolly, a[i], a[i+1]);
    }
    double S_of_target_from_Center = 0.0;
    for (int i = 1; i <= n; i++)
    {
        S_of_target_from_Center += triangle_S(Center, a[i], a[i+1]);
    }
    if (fabs(S_of_target_from_Center - S_of_target) < eps)
    {
        printf("0.000\n");
        return 0;
    }

    long double min = 9999999999999999999999.9;
    for(i = 1; i <= n; i++)
    {
    //////////////////////////////////
        double d_t_l = min_dist_to_line(a[i], a[i+1], Center);
        if(min - d_t_l > eps)
        {
            min = d_t_l;
        }
        /////////////////////
    }
    printf("%.3lf\n", 2.0*min);

    return 0;
}

Edited by author 23.02.2007 15:37

Вам не кажется, что у задачи какие кривые тесты?

Мое решение заработало, только после того как я перевел вычисления в действительные числа (такие как скалярное и косое произведения), что вообще-то смешно. При этом позицианируется, что ВСЕ координаты - целые числа в отрезке [-2000,2000] (среди участников дискуссий проверочные тесты были для больших ограничений - это подтверждает, что с тестами что-то не так).

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;
}

IF R=0.000999999999
I think (2*R).3f =(0.00199999).3f=0.001    (MY Solution gives 0.001)
BUT 2*(R.3f)=2*(0.0009999999.3f)=0.000

Edited by author 24.06.2008 15:14

{$APPTYPE CONSOLE}
{$n+}
uses
  SysUtils;

type
  tpoint=record
           x,y:{longint} extended;
         end;
const
  maxn=200;
var
  a:array[1..maxn] of tpoint;
  n:longint;
  min:extended;
  f:tpoint;
procedure init;
var
  i:longint;
begin
  assign(input,'input.txt');
  reset(input);
  assign(output,'output.txt');
  rewrite(output);
  readln(f.x,f.y,n);
  for i:=1 to n do
    readln(a[i].x,a[i].y);
  inc(n);
  a[n+1].x:=a[1].x;
  a[n+1].y:=a[1].y;
  min:=maxlongint;
end;
function scalmul(p1,p2,p3,p4:tpoint):extended;
begin
  scalmul:=(p2.x-p1.x)*(p4.x-p3.x)+(p2.y-p1.y)*(p4.y-p3.y);
end;
function rast(p1,p2:tpoint):extended;
begin
  rast:=sqrt(sqr(p2.x-p1.x)+sqr(p2.y-p1.y));
end;
function vecmul(p1,p2,p3,p4:tpoint):extended;
begin
  vecmul:=(p2.x-p1.x)*(p4.y-p3.y)-(p2.y-p1.y)*(p4.x-p3.x);
end;
function prov:boolean;
var
  i,j:longint;
  b:boolean;
begin
  b:=true;
  for i:=1 to n-1 do
    if vecmul(a[i],f,a[i],a[i+1])>=0 then begin
      if b then b:=false;
    end;
  prov:=b;
end;
procedure solve;
var
  i,j,im,l,r:longint;
  h:extended;
begin
  if prov then begin
    writeln(0.0:0:3);
    halt;
  end;
  dec(n);
  for i:=1 to n do
    if rast(f,a[i])<min then begin
       min:=rast(f,a[i]);
       im:=i;
    end;
  l:=i-1;
  r:=i+1;
  if l<1 then inc(l,n);
  if r>n then dec(r,n);
  if (scalmul(a[l],f,a[l],a[im])>0) and (scalmul(a[im],f,a[im],a[l])>0) then begin
    h:=vecmul(f,a[im],f,a[l])/rast(a[im],a[l]);
    if min>h then min:=h;
  end;
  if (scalmul(a[r],f,a[r],a[im])>0) and (scalmul(a[im],f,a[im],a[r])>0) then begin
    h:=vecmul(f,a[im],f,a[r])/rast(a[im],a[r]);
    if min>h then min:=h;
  end;
end;
procedure done;
begin
  writeln(abs(min*2):0:3);
end;
begin
  init;
  solve;
  done;
end.

Why I have "Crash (FLT_INVALID_OPERATION)"?
I not use division by zero and I use sqrt(x) only where x>=0.

Sorry for bad English.

Edited by author 23.02.2005 21:35

Edited by author 23.02.2005 21:35

I have 3 questions:
1) What does it mean "inside the polygon". If the target point lies on one of the edges is it inside the polygon.
2) I just found the distances from each edge to the target point and chose the minimal one. If the the target was inside the polygon, I output 0.000. Is that correct
3) I find the minimal distance, after that I multiply it on 2. How to output: should I use any round functions. I just used fprintf(stdout,"%.3f",res), where res is the diameter found and got WA at 4. If I tried to round it up to the third digit, I had WA at 2. What's the correct approach?

Why the answer on sample  test is 2.000? I think it should be 1.000. Could anybody explain me? Thanks.