ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1173. Lazy Snail

Why do I get WA?
Posted by Alexandru Mosoi 24 Jan 2002 18:53
This is my program.

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

typedef struct
{
long int x, y;
int u, id;
} snail;

snail s[1001];
int d[1002];
int n, k;

int cmp_snail(const void *a, const void *b)
{
snail *c = (snail *)a;
snail *d = (snail *)b;

if(c -> x == d -> x) return c -> y - d -> y;
return c -> x - d -> x;
}

int main(void)
{
int i;

memset(s, 0, sizeof(s));
scanf("%ld%ld", &s[0] . x, &s[0] . y); s[0] . id = 0;
scanf("%d", &n);

for(i = 1; i <= n; i ++)
scanf("%ld%ld%d", &s[i] . x, &s[i] . y, &s[i] . id);

qsort(s, n + 1, sizeof(snail), cmp_snail);

d[0] = 0; k = 1;
s[0] . u = 1;

for(i = 1; i <= n; i ++)
{
int find = 1;
d[k ++] = i;
while(find && k > 2)
{
long int x1 = s[d[k - 3]] . x; long int y1 = s[d[k - 3]] . y;
long int x2 = s[d[k - 2]] . x; long int y2 = s[d[k - 2]] . y;
long int x  = s[d[k - 1]] . x; long int y  = s[d[k - 1]] . y;
long int a = y1 - y2;
long int b = x2 - x1;
long int c = y2 * x1 - y1 * x2;
long int v = a * x + b * y + c;

if(v > 0)
{
d[k - 2] = d[k - 1];
k --;
} else if(v == 0)
{
printf("-1\n");
return 0;
} else find = 0;
}
}
printf("k = %d; %d\n", k, s[0] . id);

for(i = 0; i < k; i ++)
s[d[i]] . u = 1;

for(i = n; i >= 0; i --)
if(!s[i] . u) d[k ++] = i;

k = -1;
for(i = 0; i <= n && k == -1; i ++)
if(s[d[i]] . id == 0) k = i;

for(i = 0; i <= n; i ++)
{
printf("%d\n", s[d[k]] . id);
k ++;
k %= n + 1;
}
printf("0\n");
}

I tested it using many random tests. I tested it usign GRX from djgpp
and all seemed OK. Why do I get WA?
Maybe could be this :) (+)
Posted by Miguel Angel 24 Jan 2002 22:57
for(i = 0; i <= n; i ++)
{
printf("%d\n", s[d[k]] . id);
/**     k ++;
k %= n + 1;      **/
k = (k+1)%(n+1);
}
printf("0\n");

I don't check very well your program, but at first glance it's look
ok, but a detail. I argumented your program, you'll see isn't the
same. Good Luck.
Re: Maybe could be this :) (+)
Posted by Alexandru Mosoi 25 Jan 2002 18:10
>      for(i = 0; i <= n; i ++)
>      {
>      printf("%d\n", s[d[k]] . id);
> /**     k ++;
>      k %= n + 1;      **/
>         k = (k+1)%(n+1);
>      }
>      printf("0\n");
>
>
> I don't check very well your program, but at first glance it's
look
> ok, but a detail. I argumented your program, you'll see isn't the
> same. Good Luck.

No, it didn't work. But thanks for thinking about.