## 10535 - Shooter

Moderator: Board moderators

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine

### 10535 - Shooter

Please, can somebody give an example of input data?
May be there is some tricky input?

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Each set starts with a postive integer, N(1<=N<=500) the number of walls. In next few lines there will be 4*N integers indicating two endpoints of a wall in cartesian co-ordinate system. Next line will contain (x, y) the coordinates of the shooter. All coordinates will be in the range [-10000,10000].
Look at the above which is the input section of the problem statement.
There are 4*N integers indicating the wall coordinate, and there are (x, y) the coordinates of the shooter.

JongMan @ Yonsei

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I realy don't get where you're getting at, Whinii F.

For one thing, the input specification is incomplete, because the order of the 4 coordinates is not specified. It can be any of the 24 permutations of x1,x2,y1,y2 ? The most 'natural' order would be x1,y1,x2,y2, which I use in my program (WA, by the way).

Or are you saying N can be 0 before the input finishes? That would contradict the specification.

-little joey.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
I don't think there's any real trick to this problem, I had it accepted at second try. The order of the coordinates is x1,y1,x2,y2 (or y1,x1,y2,x2 or x2,y2,x1,y1 etc, it doesn't make any difference), and I terminate on N = 0.

The only problem with my first submission was that it went wrong for input like

Code: Select all

``````6
-10 10 10 10
10 10 10 -10
-10 -10 10 -10
-10 -10 -10 10
-5 -5 -15 -15
5 5 15 15
0 0``````
Where the correct answer is 3.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Oops, I was wrong.

During the contest after I got WA, I was curious about that the shooter's position was not specified as integers.

I changed ints to floats (changing to doubles yielded TLE) and got AC. And still, my int code gets WA while my float code gets AC without any change but the variables. (And the input routine, of course )

So I thought it was a little trick, that the shooter's positions were given in real numbers. But this time I tried with
[c]
scanf("%f %f", &x, &y);
assert(floor(x) == x && floor(y) == y);
[/c]

and got AC!

This is really strange, yeah. Maybe related to some overflow or something?
Last edited by Whinii F. on Tue Aug 12, 2003 6:50 pm, edited 1 time in total.
JongMan @ Yonsei

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Stupid, stupid, stupid me....

I indeed used doubles in comparisons without the appropriate measures: [pascal]while (double1<=double2) do ...[/pascal]in stead of [pascal]while (double1<=(double2+EPS)) do ...[/pascal]and the like.

For the record: x- and y- values are integers and I use them as integers. I use doubles, not reals (float), where appropriate.

Thanks Whinii F. for pointing me to the right direction.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
I used integers all the way, so it's certainly possible. If I remember correctly, the maximum value of the intermediate values in my code is +- 2*10000^2, which is well within range.

Though I guess it depends on the algorithm (I just brute forced it, checking all possible directions).

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am
can anyone see any problem with this? I get WA and I don''t know why.

[cpp]
int N, c[501][4], x, y;

bool check(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
int x = (y1-y3)*(x4-x3) - (x1-x3)*(y4-y3);
int y = (x3-x1)*(y2-y1) - (y3-y1)*(x2-x1);
int z = (y4-y3)*(x2-x1) - (x4-x3)*(y2-y1);
if (z==0) { // parallel
if (x!=0 || y!=0) { // lines not coincident
return false;
}
// check one of x3, x4 is not "behind" the ray
return ((x3-x1)*(x2-x1) >= 0 || (x4-x1)*(x2-x1) >= 0);
}
// check that on ahead part of ray and on line segment
return x*z>=0 && y*z>=0 && y*y<=z*z;
}

int main() {
while (scanf("%d",&N)==1) {
if (N==0) break;
for (i=0;i<N;i++) for (j=0;j<4;j++) scanf("%d",&c[j]);
scanf("%d %d",&x,&y);
// try all points as directions
for (i=0;i<N;i++) {
cnt = 0;
for (j=0; j<N; j++) {
if (check(x,y,c[0],c[1],c[j][0],c[j][1],c[j][2],c[j][3])) cnt++;
}
cnt = 0;
for (j=0; j<N; j++) {
if (check(x,y,c[2],c[3],c[j][0],c[j][1],c[j][2],c[j][3])) cnt++;
}
}
}
}

[/cpp]

oriol78
New poster
Posts: 32
Joined: Mon Mar 31, 2003 7:39 pm

### 10535....

hi, can anybody tell me what is the output for this input plz?:

2
0 0 0 2
0 0 2 0
0 0
0

thx

and... well. this is my code, can u check it too plz? thx again

[cpp]

#include <iostream>
#include <vector>
#include <utility>
#include <math.h>
#include <algorithm>
#include <list>
#include <map>
using namespace std;

pair<double,double> rang(pair<pair<int,int>,pair<int,int> > wall, pair<int,int> shooter)
{
pair<double, double> res;
double PI = 2*acos(0.0);
double x1, y1, x2, y2, x3, y3;
x1 = wall.first.first;
y1 = wall.first.second;
x2 = wall.second.first;
y2 = wall.second.second;
x3 = shooter.second;
y3 = shooter.second;
res.first = atan(fabs(x1-x3)/fabs(y1-y3))*180/PI;
res.second = atan(fabs(x2-x3)/fabs(y2-y3))*180/PI;
if(x1-x3 < 0 && y1-y3 > 0)
res.first = 180-res.first;
if(x1-x3 < 0 && y1-y3 < 0)
res.first = 180+res.first;
if(x1-x3 > 0 && y1-y3 < 0)
res.first = 360-res.first;
if(x2-x3 < 0 && y2-y3 > 0)
res.second = 180-res.second;
if(x2-x3 < 0 && y2-y3 < 0)
res.second = 180+res.second;
if(x2-x3 > 0 && y2-y3 < 0)
res.second = 360-res.second;
if(res.second < res.first)
swap(res.first, res.second);
return res;
}
int count(vector<pair<double,double> > rangs)
{
map<double,int> v;
map<double,int>::iterator it,it2,it3;
int res = 0;
for(int i = 0; i< rangs.size(); i++)
{
v[rangs.first] = 0;
v[rangs.second] = 0;
}
for(int i2 = 0; i2< rangs.size(); i2++)
{
it = v.find(rangs[i2].first);
it2 = v.find(rangs[i2].second);
it2++;
for(it3 = it; it3 != it2; it3++)
{
it3->second++;
}
}
for(it3 = v.begin(); it3 != v.end(); it3++)
{
if(it3->second > res)
res = it3->second;
}
return res;
}

int proces(int walls)
{
vector<pair<pair<int,int>,pair<int,int> > > listWalls(walls);
vector<pair<double,double> > rangs(walls);
pair<int,int> shooter;
for(int i = 0; i< walls; i++)
cin >> listWalls.first.first >> listWalls.first.second >> listWalls.second.first >> listWalls.second.second;
cin >> shooter.first >> shooter.second;
for(int i2 = 0; i2 < walls; i2++)
rangs[i2] = rang(listWalls[i2], shooter);
for(int i3 = 0; i3 < walls; i3++)
{
if(rangs[i3].second-rangs[i3].first > 180)
{
rangs.push_back(make_pair(rangs[i3].second,360));
rangs[i3].second = rangs[i3].first;
rangs[i3].first = 0;
}
}
sort(rangs.begin(), rangs.end());
return count(rangs);
}

int main()
{
int walls;
cin >> walls;
while(walls)
{
cout << proces(walls) << endl;;
cin >> walls;
}
return 0;
}
/* @END_OF_SOURCE_CODE */
[/cpp]

cauchy
New poster
Posts: 9
Joined: Thu May 29, 2003 11:37 pm
Location: Poznan

### O(nlogn)?

Is it possible to get O(nlogn) for this problem? I got acc but my program runs extreamly slow (nearly 5sec) and I have only O(n^2). I would be grateful for any hint

Darwin
New poster
Posts: 1
Joined: Mon Apr 19, 2004 10:37 am
Location: China
Contact:

### Re: O(nlogn)?

cauchy wrote:Is it possible to get O(nlogn) for this problem? I got acc but my program runs extreamly slow (nearly 5sec) and I have only O(n^2). I would be grateful for any hint
You can use interval tree to reduce the time complexity to O(nlogn)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
There are easier algorithms in O(n log n)..

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
This input is wrong.
Because "The shooter will never stand on a wall."

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:
Does anybody have any tricky data to 10535?

I know that my code is quite long. I added a lot of debugging data to it.
I have tried to rewrite my code a few times. But I still get WA.

[cpp]
#include <cstdio>
#include <set>
#include <map>
#include <math.h>
#include <assert.h>
#include <vector>
#include <algorithm>

using namespace std;

//#define DEBUG

#ifndef DEBUG
//#define NDEBUG
#endif

//%llu
//unsigned long long -

#define MAX 512
#define MAXPOS 12

const double PI = 3.1415926535897932384626433832795;
//double PI = 2*acos(0.0);

struct triple {
int point[2];
double pos;
triple( int mpoint[2], double mpos):pos(mpos) {point[0] = mpoint[0]; point[1] = mpoint[1];}
};

struct comp {
bool operator() (triple p1, triple p2) const{
return (p1.pos < p2.pos);
}
} ;

struct pointcomp {
bool operator() (pair<int,int> p1, pair<int,int> p2)const {
if( p1.first != p2.first)
return (p1.first < p2.first);
else
return (p1.second < p2.second);
}
} ;

int nvd(int a, int b) {
// fprintf(stderr,"nvd a %d b %d\n",a,b);
if( (a == 0) || (b == 0) )
return max(a,b);
else
return (nvd(b,a%b));
}

void increase(int occupied[3*MAX], pair<int,int> wallsize , pair<int,int> curpoints , int poz = 1) {
assert( poz < 3*MAX);
assert( wallsize.first <= wallsize.second);
assert( curpoints.first <= curpoints.second);

//to increase performance
if( wallsize.first <= curpoints.first && wallsize.second >= curpoints.second) {
occupied[poz]++;
return;
}
else {
if( curpoints.first == curpoints.second )
return;

int p = (curpoints.first + curpoints.second ) /2; //floor will be used
increase(occupied, wallsize, make_pair(curpoints.first, p) , 2*poz);
increase(occupied, wallsize, make_pair(p+1, curpoints.second) , 2*poz+1);
}
}

int getmaximum(int occupied[3*MAX], pair<int,int> wallsize , pair<int,int> curpoints , int poz = 1) {
assert( poz < 3*MAX);
assert( wallsize.first <= wallsize.second);
assert( curpoints.first <= curpoints.second);

//to increase performance
if( wallsize.first >= curpoints.first && wallsize.second <= curpoints.second) {
int sum = occupied[poz];

if( curpoints.first == curpoints.second)
return sum; //no futher data to analyze

int p = (curpoints.first + curpoints.second) /2; //floor will be used
sum += getmaximum(occupied, wallsize, make_pair(curpoints.first, p) , 2*poz);
sum += getmaximum(occupied, wallsize, make_pair(p+1, curpoints.second) , 2*poz+1);
return sum;
}
else
return 0;
}

void read_data( int points[MAX][2][3] , int shooter[2] , int n ) {
for( int i = 0 ; i < n ; i ++) {
scanf("%d %d %d %d",&points[0][0],&points[0][1],&points[1][0],&points[1][1]);
}
scanf("%d %d",&shooter[0],&shooter[1]);
}

int analyze(int n) {
int points[MAX][2][3]; // x y id
int shooter[2]; //position of shooter
int occupied[3*MAX]; //
memset(occupied,0,sizeof(occupied));

//vector translation
for( int i = 0 ; i < n ; i ++) {
for( int j =0 ;j < 2; j++) {
points[j][0] -= shooter[0];
points[j][1] -= shooter[1];
}
#ifdef DEBUG
fprintf(stderr,"dane po przesunieciu %d %d %d %d\n",points[0][0],points[0][1],points[1][0],points[1][1]);
#endif
}
shooter[0] -= shooter[0];
shooter[1] -= shooter[1];

//make data relative prime
for( int i = 0 ; i < n ; i ++) {
for( int j = 0 ; j < 2 ;j ++) {
int mnvd = nvd( abs(points[i][j][0]),abs(points[i][j][1]) );
assert( mnvd >= 1);
assert( points[i][j][0] % mnvd == 0);
assert( points[i][j][1] % mnvd == 0);
points[i][j][0] /= mnvd;
points[i][j][1] /= mnvd;
assert( nvd( abs(points[i][j][0]),abs(points[i][j][1]) ) == 1);
}
}

vector <triple> Q;
for( int i = 0 ; i < n ; i ++) {
for( int j = 0 ; j < 2 ; j++)
Q.push_back( triple(points[i][j],atan2(points[i][j][1],points[i][j][0] ) ) );
}

sort(Q.begin(),Q.end(),comp());
map < pair<int,int> , int , pointcomp > idpoints;

assert(Q.size() == 2*n);

int lastpoint[2] = { 0x7fffffff , 0x7fffffff } ; // this case will never happen
int nr = 0;
#ifdef DEBUG
fprintf(stderr,"zaraz bedzie indexowanie\n");
#endif
for( int i = 0 ;i < Q.size() ; i++) {
#ifdef DEBUG
fprintf(stderr,"%d %d\n", Q[i].point[0], Q[i].point[1]);
#endif
if( Q[i].point[0] != lastpoint[0] || Q[i].point[1] != lastpoint[1] ) {
idpoints[ make_pair(Q[i].point[0],Q[i].point[1]) ] = nr;
for(int j =0 ;j < 2; j++)
lastpoint[j] = Q[i].point[j];
nr++;
}
assert( idpoints.find( make_pair(Q[i].point[0],Q[i].point[1]) ) != idpoints.end()); // make sure that this point is in list
assert( idpoints[ make_pair(Q[i].point[0],Q[i].point[1]) ] >= 0);
assert( idpoints[ make_pair(Q[i].point[0],Q[i].point[1]) ] < nr);
}
//id is from 0 to nr -1

#ifdef DEBUG
fprintf(stderr,"it's time to get indexes for points\n");
#endif
for( int i = 0 ; i < n ; i ++) {
for( int j = 0 ; j < 2 ;j ++) {
points[i][j][2] = idpoints[ make_pair( points[i][j][0] , points[i][j][1] ) ];
#ifdef DEBUG
fprintf(stderr,"!!%d %d = %d %lf\n",points[i][j][0], points[i][j][1],points[i][j][2] , atan2(points[i][j][1],points[i][j][0]));
#endif
assert( idpoints.find( make_pair( points[i][j][0] , points[i][j][1] ) ) != idpoints.end());
assert( points[i][j][2] >= 0);
assert( points[i][j][2] < nr);
}
}

#ifdef DEBUG
fprintf(stderr,"swapping\n"); // to make sure that end points are ordered not in clock order
#endif
for( int i = 0 ; i < n ; i ++) {
if( points[i][0][2] > points[i][1][2]) {
for(int k=0;k<3;k++) {
swap(points[i][0][k],points[i][1][k]);
}
}
}

#ifdef DEBUG
fprintf(stderr,"increasing values in table\n");
#endif
for( int i = 0 ; i < n ; i ++) {
#ifdef DEBUG
fprintf(stderr,"i = %d points %d %d\n",i,points[i][0][2] ,points[i][1][2]);
#endif
assert( ((
atan2( points[i][1][1] ,points[i][1][0])
- atan2( points[i][0][1] ,points[i][0][0])
) ) >= 0);
if( (atan2( points[i][1][1] ,points[i][1][0]) - atan2( points[i][0][1] ,points[i][0][0]) ) <= PI ) {
#ifdef DEBUG
fprintf(stderr,"case 1 i = %d\n",i);
#endif
increase(occupied,make_pair(points[i][0][2],points[i][1][2]), make_pair(0, MAX-1) );
//points[i][0][2] - points[i][1][2]
}
else {
#ifdef DEBUG
fprintf(stderr,"case 2 i = %d\n",i);
#endif
increase(occupied, make_pair(0 , points[i][0][2]) , make_pair(0, MAX-1) );
increase(occupied, make_pair(points[i][1][2], nr-1) , make_pair(0, MAX-1) );
// 0 - points[i][0][2] ; points[i][1][2] - (nr -1)
}
}

#ifdef DEBUG
fprintf(stderr,"calculating max walls\n");
#endif
int maximum = 0;
for( int i = 0 ; i < nr ; i ++) {
int maxwalls = getmaximum(occupied, make_pair(i,i) , make_pair(0 , MAX-1) );
#ifdef DEBUG
fprintf(stderr,"point: %d = %d\n",i,maxwalls);
#endif
if( maximum < maxwalls )
maximum = maxwalls ;
}

return maximum;
}

int main() {
#ifdef DEBUG
freopen("./data.in","r",stdin);
#endif
int n;
int i = 0;
while( true) {
#ifdef DEBUG
fprintf(stderr,"\n!!Next data to analyze\n");
#endif
scanf("%d",&n);
if( n == 0)
break;
printf("%d\n",analyze(n));
}

return 0;
}
[/cpp]

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
can anybody tell me what is the answer to this test case:
• 5
-1 1 1 1
-1 -1 1 -1
-1 -1 -1 1
1 0 1 -1
0 2 1 0
1 2
i think it should be 4, is that right?