109 - SCUD Busters

[diamind]

[cpp]
#include <iostream>
#include <fstream>
#include <stream.h>
#include <stdlib.h>
#include <vector>

struct Point {int x, y;};
struct Polygon {vector<Point> points;};
struct Kingdom
{
vector<Point> sites;
vector<Point> convexHull;
vector<Point> polygon;
Point plant;

int calcArea(int n0, int n1, int n2)
{
return convexHull[n0].x*polygon[n1].y + polygon[n1].x*polygon[n2].y + polygon[n2].x*convexHull[n0].y
- polygon[n2].x*polygon[n1].y - polygon[n1].x*convexHull[n0].y - convexHull[n0].x*polygon[n2].y;
}

int calcPolygonArea(int n0, int n1, int n2)
{
return polygon[n0].x*polygon[n1].y + polygon[n1].x*polygon[n2].y + polygon[n2].x*polygon[n0].y
- polygon[n2].x*polygon[n1].y - polygon[n1].x*polygon[n0].y - polygon[n0].x*polygon[n2].y;
}

int calcAreaConvHull(int n0, int n1, int x, int y)
{
return convexHull[n0].x*convexHull[n1].y + convexHull[n1].x*y + x*convexHull[n0].y
- x*convexHull[n1].y - convexHull[n1].x*convexHull[n0].y - convexHull[n0].x*y;
}

bool inKingdom(Point s)
{
for (int i=0; i<sites.size(); i++)
{
if (sites.x==s.x && sites.y==s.y) return true;
}
return false;
}

void findEdge()
{
bool good=true;
for (int i=0; i<polygon.size(); i++)
for (int j=0; j<polygon.size(); j++)
if (i!=j)
{
//cout<<"Testing ("<<polygon.x<<","<<polygon.y<<") and ("
// <<polygon[j].x<<","<<polygon[j].y<<") for convex hull edge: "<<endl;
good=true;
int k;
for (k=0; k<polygon.size(); k++)
if ((i != j) && (j!=k) && (k!=i))
{
int area = calcPolygonArea(i, j, k);
if (area<0)
{
good=false;
//cout<<" No"<<endl;
break;
}
}
if(good)
{
convexHull.push_back(polygon);
convexHull.push_back(polygon[j]);
//cout<<" Ok"<<endl;
return;
}
}
}

void buildConvexHull()
{
polygon.push_back(plant);
for (int i=0; i<sites.size(); i++) polygon.push_back(sites);
findEdge();

Point testPoint;
testPoint.x=convexHull[1].x;
testPoint.y=convexHull[1].y;

bool builtCH=false;
while(!builtCH)
{
int k;
for (k=0; k<polygon.size() && !builtCH; k++)
{
bool good=true;
int n=convexHull.size();

testPoint.x=polygon[k].x;
testPoint.y=polygon[k].y;
//cout<<"testing ("<<testPoint.x<<","<<testPoint.y<<"):"<<endl;

if (!(testPoint.x==convexHull[n-1].x && testPoint.y==convexHull[n-1].y) &&
!(testPoint.x==convexHull[n-2].x && testPoint.y==convexHull[n-2].y)
)
{
for (int m=0; m<polygon.size(); m++)
if (calcArea(n-1, k, m)<0)
{
good=false;
//cout<<"No"<<endl;
break;
}
}else {good=false;}

if(good)
{
convexHull.push_back(polygon[k]);
n=convexHull.size();
//cout<<"Ok"<<endl;
if (testPoint.x==convexHull[0].x && testPoint.y==convexHull[0].y) builtCH=true;
}
}
}
}

bool got(int x, int y)
{
for (int i=0; i<convexHull.size()-1; i++)
if (calcAreaConvHull(i, i+1, x, y)<=0)
{
//cout<<"No"<<endl;
return false;
}
//cout<<"Yes!"<<endl;;
return true;
}

double convexHullArea()
{
double total=0;
int n = convexHull.size();
for(int i=0; i<n-1; i++)
total += convexHull.x*convexHull[i+1].y - convexHull[i+1].x*convexHull.y;
total /= 2;
}
};


bool inBombs(Point place, vector<Point> bombs)
{
for (int i=0; i<bombs.size(); i++)
if (place.x==bombs.x && place.y==bombs.y)
return true;
return false;
}


void main()
{
ifstream F; F.open("C:\\My Documents\\input.txt"); cin = F;

vector<Kingdom> kingdoms;

while(!cin.eof())
{
// read kingdom information:
int N;
cin>>N; // number of sites
if (N==-1) break;
//cout<<"N="<<N<<endl;
Kingdom tmpKingdom;
Point tmpSite;
cin>>tmpSite.x; if (cin.eof()) break;
cin>>tmpSite.y; if (cin.eof()) break;
tmpKingdom.plant = tmpSite;
for(int i=0; i<N-1; i++)
{
cin>>tmpSite.x; if (cin.eof()) break;
cin>>tmpSite.y;
if (!tmpKingdom.inKingdom(tmpSite)) tmpKingdom.sites.push_back(tmpSite);
}
kingdoms.push_back(tmpKingdom);
}

for (int i=0; i<kingdoms.size(); i++)
{
kingdoms[i].buildConvexHull();
}

double totalArea=0;
vector<Point> bombs;
while(!cin.eof())
{
// read bomb coords:
int x, y;
cin>>x; if (cin.eof()) break;
cin>>y;
Point place; place.x=x; place.y=y;
if (!inBombs(place, bombs))
{
bombs.push_back(place);
for(int i=0; i<kingdoms.size(); i++)
{
//cout<<"check if bomb ("<<x<<","<<y<<") got kingdoms["<<i<<"]"<<endl;
if (kingdoms[i].got(x, y))
totalArea += kingdoms[i].convexHullArea();
}
}
}
cout<<totalArea<<endl;
}
[/cpp]

Here is my code. It returns a WA. I tested it on every case and I dont know where to go from here. Anyone can spot a bug? BTW, it returns 223870 on the last test, not 223865.50 as others. Can this be mistake in my program? I wrote a convexHull building program for the first time in my life and suspect there can be problems with points on one line. I used a gift wrappper algorithm as I understood it. Let me know if you see smth wrong with it. I give up and go to the nect problem.

[TuIgEv]

Please, help me. I always get WA in this problem. My algorithm:
1. Make convex hull with Graham scanning for each kingdom
2. For each kingdom count it's square
3. For each missle enable kingdom (or no kingdom)
4. For all enabled kingdoms sum their square.

May be, that sms wrong with:
1. When missle comes on the wall
2. When missle comse on the vertex

Here is my code in PASCAL

program zzz;
const eps = 1e-12;
type king = record
x,y : array [1..100] of longint;
n,num : longint;
s : double;
con : array [1..101] of longint;
end;
var i,j,k,n,m,x,y : longint;
x1,y1 : array [1..100] of longint;
a : array [1..20] of king;
vis : array [1..20] of longint;
a1,d1,d2,a2 : double;
ans : double;

procedure push(i,x : longint);
begin
inc(a.num);
a.con[a.num] := x;
end;

procedure pop(i : longint);
begin
dec(a.num);
end;

procedure swap(var i,j : longint);
var t : longint;
begin
t := i;
i := j;
j := t;
end;

function ang(x1,y1,x2,y2 : longint) : double;
var h : double;
begin
if x1 = x2 then begin
h := pi/2;
end else if x2 > x1 then begin
h := arctan((y2-y1)/(x2-x1));
end else begin
h := pi-arctan((y2-y1)/(x1-x2));
end;
ang := h;
end;

function dis(x1,y1,x2,y2 : longint) : double;
begin
dis := sqrt(sqr(x2-x1)+sqr(y2-y1));
end;

function more(k,x1,y1,x2,y2 : longint) : boolean;
var a1,a2,d1,d2 : double;
p : boolean;
begin
if i = j then begin
more := false;
exit;
end;
a1 := ang(a[k].x[1],a[k].y[1],x1,y1);
d1 := dis(a[k].x[1],a[k].y[1],x1,y1);
a2 := ang(a[k].x[1],a[k].y[1],x2,y2);
d2 := dis(a[k].x[1],a[k].y[1],x2,y2);
if abs(a1-a2) < eps then begin
if d1 > d2 then p := true else p := false;
end else if a1 > a2 then p := true else p := false;
more := p;
end;

procedure qsort(k,l,r : longint);
var i,j,zx,zy,e : longint;
begin
e := random(r-l)+l;
zx := a[k].x[e];
zy := a[k].y[e];
i := l;
j := r;
repeat
while more(k,zx,zy,a[k].x,a[k].y) do inc(i);
while more(k,a[k].x[j],a[k].y[j],zx,zy) do dec(j);
if i <= j then begin
swap(a[k].x,a[k].x[j]);
swap(a[k].y,a[k].y[j]);
inc(i);
dec(j);
end;
until i > j;
if l < j then qsort(k,l,j);
if i < r then qsort(k,i,r);
end;

function dright(k,i1,i2,i3 : longint) : boolean;
var v : longint;
begin
v := (a[k].x[i3]-a[k].x[i1])*(a[k].y[i2]-a[k].y[i1]);
v := v - (a[k].y[i3]-a[k].y[i1])*(a[k].x[i2]-a[k].x[i1]);
dright := (v>=0);
end;

function ins(k,x,y : longint) : boolean;
var i,j,v,v1,x1,y1,x2,y2 : longint;
begin
x1 := a[k].x[a[k].con[1]];
y1 := a[k].y[a[k].con[1]];
x2 := a[k].x[a[k].con[2]];
y2 := a[k].y[a[k].con[2]];
v := (x-x1)*(y2-y1) - (y-y1)*(x2-x1);
for i := 2 to a[k].num do begin
x1 := a[k].x[a[k].con];
y1 := a[k].y[a[k].con];
x2 := a[k].x[a[k].con[i+1]];
y2 := a[k].y[a[k].con[i+1]];
v1 := (x-x1)*(y2-y1) - (y-y1)*(x2-x1);
if v1*v <= 0 then begin
ins := false;
exit;
end;
end;
ins := true;
end;

begin
randomize;
k := 0;
while true do begin
readln(n);
if n = -1 then break;
inc(k);
a[k].n := n;
j := 1;
for i := 1 to n do begin
readln(a[k].x[i],a[k].y[i]);
if a[k].y[i] < a[k].y[j] then begin
j := i;
end else if (a[k].y[i] = a[k].y[j])and(a[k].x[i] < a[k].x[j]) then
j := i;
end;
swap(a[k].x[1],a[k].x[j]);
swap(a[k].y[1],a[k].y[j]);
m := 1;
qsort(k,2,a[1].n);
m := 0;
a2 := -1;
j := 1;
for i := 2 to a[k].n do begin
a1 := ang(a[k].x[1],a[k].y[1],a[k].x[i],a[k].y[i]);
if abs(a1-a2) > eps then begin
inc(m);
x1[m] := a[k].x[j];
y1[m] := a[k].y[j];
a2 := a1;
j := i;
end else j := i;
end;
inc(m);
x1[m] := a[k].x[a[k].n];
y1[m] := a[k].y[a[k].n];
a[k].n := m;
for i := 1 to m do begin
a[k].x[i] := x1[i];
a[k].y[i] := y1[i];
end;
for i := 1 to 3 do begin
push(k,i);
end;
for i := 4 to a[k].n do begin
while dright(k,a[k].con[a[k].num-1],a[k].con[a[k].num],i) do begin
pop(k);
end;
push(k,i);
end;
a[k].con[a[k].num+1] := a[k].con[1];
a[k].s := 0;
for i := 1 to a[k].num do begin
a[k].s := a[k].s+(a[k].x[a[k].con[i]]*a[k].y[a[k].con[i+1]]-
a[k].y[a[k].con[i]]*a[k].x[a[k].con[i+1]])/2;
end;
a[k].s := abs(a[k].s);
end;
fillchar(vis,sizeof(vis),0);
while not eof do begin
readln(x,y);
for i := 1 to k do begin
if ins(i,x,y) then vis[i] := 1;
end;
end;
ans := 0;
for i := 1 to k do begin
if vis[i] <> 0 then ans := ans + a[i].s;
end;
write(ans:0:2);
end.

[junbin]

Check your floating point numbers..
and format your code using the tags

[TuIgEv]

Actually, I have tags. It just didn't copy.

Thanks, I'll look better on my floating operations. But I use EPS ans all like this.

[Larry]

It's possible to do this problem without floating point, at least until the area calculations..

[Chung Ha, Yun]

I got RUN TIME ERROR (SIGSEGV).

I don't know why SIGSEGV.

I tested any input set that I got it in this site.

Plz Help Me...




[c]
#include <stdio.h>
#include <math.h>
#include <string.h>

typedef struct _KINGDOM {
int x;
int y;
} KINGDOM;

#define MAX 20

KINGDOM table[MAX][110];
int table_count[MAX];

void change_to_convexhull(int index);
bool is_destroy(int index, KINGDOM missile);
double convex_area(int index);
int direction(KINGDOM i, KINGDOM j, KINGDOM k);
void find_p0(KINGDOM *kingdom, int length);
void swap_kingdom(KINGDOM *a, KINGDOM *b);
void sort_by_polarangle(KINGDOM *kingdom, int length);
void bubble_swap(double *a, double *b, KINGDOM *ta, KINGDOM *tb);

int main()
{
int kingdoms = 0, sites, i;

// input kingdom sites
while (scanf("%d", &sites) != EOF && sites != -1) {
table_count[kingdoms] = sites;
for (i = 0; i < sites; i++)
scanf("%d %d", &table[kingdoms].x, &table[kingdoms].y);

change_to_convexhull(kingdoms);

kingdoms++;
}

// input missile attack
int nopower[MAX];
memset(nopower, 0, sizeof(int) * MAX);
KINGDOM missile;
while (scanf("%d %d", &missile.x, &missile.y) != EOF)
for (i = 0; i < kingdoms; i++)
if (is_destroy(i, missile))
nopower = 1;

// summation
double sum = 0.0;
for (i = 0; i < kingdoms; i++)
if (nopower == 1 && table_count >= 3)
sum += convex_area(i);

// output
printf("%.2lf\n", sum);
return 0;
}

bool is_destroy(int index, KINGDOM missile)
{
int length = table_count[index];
table[index][length].x = table[index][0].x;
table[index][length].y = table[index][0].y;

int result = 0;
bool isdestroy = true;
for (int i = 0; i < length && isdestroy; i++)
if (direction(table[index], table[index][i + 1], missile) <= 0)
isdestroy = false;
return isdestroy;
}

double convex_area(int index)
{
double sum = 0.0;
int length = table_count[index];
table[index][length].x = table[index][0].x;
table[index][length].y = table[index][0].y;

for (int i = 1; i <= length; i++)
sum += (table[index].x * table[index].y - table[index].x * table[index].y);
return sum * 0.5;
}

void change_to_convexhull(int index)
{
KINGDOM Q[110], S[110];
int length = table_count[index], top;
memcpy(Q, table[index], sizeof(KINGDOM) * length);
// p0 is the minimum(?) y-coordinate or the leftmost such point in case of a tie
find_p0(Q, length);
// sort (p1, p2, ... pn)
sort_by_polarangle(Q, length);

// PUSH (p0, S)
S[0].x = Q[0].x, S[0].y = Q[0].y;
// PUSH (p1, S)
S[1].x = Q[1].x, S[1].y = Q[1].y;
// PUSH (p2, S)
S[2].x = Q[2].x, S[2].y = Q[2].y;
top = 2;

for (int i = 3; i < length; i++) {
while (direction(S[top - 1], S[top], Q[i]) <= 0) top--;
// PUSH (pi, S);
top++;
S[top].x = Q[i].x, S[top].y = Q[i].y;
}
if (top > 2 && direction(S[top - 1], S[top], S[0]) <= 0) top--;

// return S
table_count[index] = top + 1;
memcpy(table[index], S, sizeof(KINGDOM) * (top + 1));
}

void sort_by_polarangle(KINGDOM *kingdom, int length)
{
int i, j;
// base is table[0]
double cos_table[110], width, distance;
for (i = 1; i < length; i++) {
distance = sqrt((kingdom[0].x - kingdom[i].x) * (kingdom[0].x - kingdom[i].x) +
(kingdom[0].y - kingdom[i].y) * (kingdom[0].y - kingdom[i].y));
width = kingdom[i].x - kingdom[0].x;
cos_table[i] = width / distance; // compute cosine value
}

// bubble sort by cosine table
for (i = 1; i < length; i++)
for (j = 1; j < length - i; j++)
if (cos_table[j] < cos_table[j + 1])
bubble_swap(&cos_table[j], &cos_table[j + 1],
&kingdom[j], &kingdom[j + 1]);
}

void bubble_swap(double *a, double *b, KINGDOM *ta, KINGDOM *tb)
{
double temp = *a;
*a = *b;
*b = temp;
KINGDOM ktemp;
ktemp.x = ta->x, ktemp.y = ta->y;
ta->x = tb->x, ta->y = tb->y;
tb->x = ktemp.x, tb->y = ktemp.y;
}

int direction(KINGDOM i, KINGDOM j, KINGDOM k)
{
return (j.x - i.x) * (k.y - i.y) - (k.x - i.x) * (j.y - i.y);
}

void find_p0(KINGDOM *kingdom, int length)
{
for (int i = 1; i < length; i++)
if (kingdom[0].y > kingdom[i].y) // coordinate system..?
swap_kingdom(&kingdom[0], &kingdom[i]);
else if (kingdom[0].y == kingdom[i].y && kingdom[0].x > kingdom[i].x)
swap_kingdom(&kingdom[0], &kingdom[i]);
}

void swap_kingdom(KINGDOM *a, KINGDOM *b)
{
KINGDOM temp;
temp.x = a->x, temp.y = a->y;
a->x = b->x, a->y = b->y;
b->x = temp.x, b->y = temp.y;
}
[/c]

[fpmc]

Hi,

I have read every posts regarding problem 109 in this forum and have checked my code against all the sample cases that people give. I even took an "accepted" solution and ran a few million tests with random inputs. I couldnt' find my bug but it seems that the following test case get different answers for my solution and the AC solution:

Code: Select all

46
234 157 288 495 38 416 82 29 434 382 287 406 306 144 287 400 48 81 137 313 276 388 26 212 71 382 93 148 396 292 449 314 308 129 44 236 265 346 227 127 32 199 344 13 414 339 420 131 444 463 350 57 269 220 101 377 24 341 132 195 8 420 48 80 317 316 162 93 220 81 281 389 403 253 91 125 256 317 279 11 68 200 421 129 5 338 178 22 217 29 450 310
-1
391 225

AC solution: 178859.50
My solution: 178887.50

I checked with maple and various other methods and I still think my answer is correct. I plotted my convex hull in matlab and it also seems correct!!! Can someone help me here? Can others who got AC post their output to the above test case?

Thanks,
Frank

[sohel]

My AC program outputs 178887.50 for your input....

I think this sort of data will not be there in the judge's input, where the landing is on the perimeter of the convex hull. And I think in your input data this rule is not obeyed.

[fpmc]

I don't think this input data is any special. There's only one polygon and one missle, and the missle is quite "inside" the polygon. Both my program and AC solution calculated the area of the convex hull, just that we had different solutions. I'm glad to hear that your solution matched mine...

Can you think of any special cases? My code uses integers only except for area calculations and I can't see any special cases that it'll miss.....

Frank

[fpmc]

Sorry, I have found a bug in my convex hull code. I now got AC. Thanks for your help.

Frank

[shanto86]

I am getting WA. where is problem? is it necessary to use non-floating point calculation? can anyone check for cases where my code fails?

Thanks in advance.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int top=0,n;

int amount[1000];
double city[21][101][2];
double area[1000];

typedef struct points points;

struct points{
double x,y;
double ang;
};

points point[110];
points convex[110];

int cmp1(const void *va,const void *vb)
{
points *a,*b;

a=(points*)va;
b=(points*)vb;

if(a->y>b->y || (a->y==b->y && a->x>b->x))
return 1;
else
return -1;
}

double angle(long int i)
{
double x1=point[i].x-point[0].x;
double y1=point[i].y-point[0].y;

if(y1==0.)
{
if(x1>0.0)
return 0.0;
else
return 180.0;
}
if(x1==0.0)
{
if(y1>0.0)
return 90.0;
else
return 270.0;
}

double r=sqrt(x1*x1+y1*y1);
double thita=acos(fabs(y1)/r);
double pi=acos(-1.);

if(x1>0. && y1>0.) return 180./pi*thita;
else if(x1<0. && y1>0.) return 180./pi*thita+90.;
else if(x1>0. && y1<0.) return 180./pi*thita+270.;
else if(x1<0. && y1<0.) return 180./pi*thita+180.;
return 0.0;
}

double turn(int i,int j,int k)
{
double ar=convex[i].x*convex[j].y + convex[j].x*point[k].y + point[k].x*convex[i].y - convex[i].y*convex[j].x - convex[j].y*point[k].x - point[k].y*convex[i].x;
return ar;
}

void convex_hull()
{
int i;
convex[0]=point[0];
convex[1]=point[1];
convex[2]=point[2];
top=2;

for(i=3;i<n;i++)
{
while(top>1 && turn(top-1,top,i)<0.0)
top--;
top++;
convex[top]=point[i];
}
}

double dist(int i)
{
return sqrt((point[i].x-point[0].x)*(point[i].x-point[0].x) + (point[i].y-point[0].y)*(point[i].y-point[0].y));
}

double dist1(double ix,double iy,double jx,double jy)
{
return sqrt( (ix-jx)*(ix-jx)+(iy-jy)*(iy-jy) );
}

int isdestroy(int k, double bx, double by)
{
double ar=0.,kr;
int i,j;
for(i=0;i<=amount[k];i++)
{
j=(i+1)%(amount[k]+1);

kr=0.0;
kr+=.5*(city[k][i][0]*city[k][j][1]+city[k][i][1]*bx+city[k][j][0]*by);
kr-=.5*(city[k][i][0]*by+city[k][i][1]*city[k][j][0]+city[k][j][1]*bx);
if(fabs(kr)<=1e-6 && fabs(dist1(bx,by,city[k][i][0],city[k][i][1])+dist1(bx,by,city[k][j][0],city[k][j][1])-dist1(city[k][j][0],city[k][j][1],city[k][i][0],city[k][i][1]))<=1e-6)
return 0;
ar+=fabs(kr);
}
if(fabs(fabs(ar)-area[k])<=1e-6)
return 1;
return 0;
}

double poly(int k)
{
double ar=0.;
int i,j;

for(i=0;i<=amount[k];i++)
{
j=(i+1)%(amount[k]+1);
ar+=.5*(city[k][i][0]*city[k][j][1]-city[k][i][1]*city[k][j][0]);
}

return fabs(ar);
}

int main()
{
int i,j;
int total=0;
int destroy[1000];
double bombx,bomby;
double ar;

while(scanf("%d",&n)!=EOF)
{
if(n==-1)
break;

total++;

for(i=0;i<n;i++)
scanf("%lf%lf",&point[i].x,&point[i].y);

qsort(point,n,sizeof(points),cmp1);

for(i=1;i<n;i++)
point[i].ang=angle(i);

for(i=1;i<n-1;i++)
for(j=i+1;j<n;j++)
if(point[i].ang>point[j].ang || (point[i].ang==point[j].ang && dist(i) >dist(j)))
{
point[n]=point[i];
point[i]=point[j];
point[j]=point[n];
}

convex_hull();

amount[total]=top;
destroy[total]=0;
for(i=0;i<=top;i++)
{
city[total][i][0]=convex[i].x;
city[total][i][1]=convex[i].y;
}
area[total]=poly(total);
}

while(scanf("%lf%lf",&bombx,&bomby)!=EOF)
{
for(i=1;i<=total;i++)
if(isdestroy(i,bombx,bomby)==1)
destroy[i]=1;
}

ar=0.0;
for(i=1;i<=total;i++)
if(destroy[i])
ar+=area[i];

printf("%.2lf\n",ar);
return 0;
}

[jonaskoelker]

It's possible to do this problem without floating-point calculations at all: using the given area formula, we can compute twice the area as an int, then output either '50' or '00' as the decimal part, based on whether the int is even or not.

[sunnycare]

who can explain it to me? (is there any chinese)
thanks..
i cant understand problem 138 either....

[jakabjr]

Basically, each kingdom (country) is delimited by it's power-plant and buildings. The smallest pollygone that encloses them is the actual kingdom.
Then you get the possitions (points) where missiles fall. Practically, you have two problems: determining if a point (missile land point) is inside a pollygone (the kingdom) and calculating the area of a pollygone.
Then you sum up all areas of kingdoms without power and you get your answer. A kingdom that is hit 2 times is added only 1 time, of course.

As for the "help" at the end, I didn't understand that formula either, and if someone would care to explain, I would appreciate it a lot.

[sunnycare]

thanks .....
it's great helpful to me