Page 1 of 2

10535 - Shooter

Posted: Mon Aug 11, 2003 12:51 pm
by Alexander Kozlov
Please, can somebody give an example of input data?
May be there is some tricky input?

Thanks in advance!

Posted: Mon Aug 11, 2003 4:08 pm
by Whinii F.
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.

Read between the lines. :)

Posted: Mon Aug 11, 2003 5:42 pm
by little joey
I realy don't get where you're getting at, Whinii F. :cry:

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.

Please elaborate, If you will.
-little joey.

Posted: Mon Aug 11, 2003 7:20 pm
by Per
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.

Posted: Tue Aug 12, 2003 11:36 am
by Whinii F.
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?

Posted: Tue Aug 12, 2003 1:57 pm
by little joey
Stupid, stupid, stupid me.... :evil:

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.

Posted: Tue Aug 12, 2003 8:19 pm
by Per
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).

Posted: Fri Aug 22, 2003 3:09 am
by Joe Smith
can anyone see any problem with this? I get WA and I don''t know why. :cry:

[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() {
int i, j, cnt, answer;
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);
answer = 0;
// 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++;
}
answer = max(answer,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++;
}
answer = max(answer,cnt);
}
printf("%d\n",answer);
}
}

[/cpp]

10535....

Posted: Sat Sep 06, 2003 1:02 pm
by oriol78
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? :-P thx again

PD: sorry about my english

[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]

O(nlogn)?

Posted: Thu Sep 18, 2003 8:58 pm
by cauchy
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 :)

Re: O(nlogn)?

Posted: Tue May 25, 2004 3:47 pm
by Darwin
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)

Posted: Tue May 25, 2004 5:59 pm
by Larry
There are easier algorithms in O(n log n)..

Posted: Fri Jul 09, 2004 10:37 am
by PMNOX
This input is wrong.
Because "The shooter will never stand on a wall."

Posted: Fri Jul 09, 2004 2:53 pm
by PMNOX
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));

read_data(points,shooter , n);


//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]

Posted: Sun Nov 21, 2004 3:11 pm
by Moha
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?