10535 - Shooter

[Alexander Kozlov]

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

Thanks in advance!

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

[little joey]

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.

Please elaborate, If you will.
-little joey.

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

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

[little joey]

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]

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]

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() {
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]

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

[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

[Darwin]

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]

There are easier algorithms in O(n log n)..

[PMNOX]

This input is wrong.
Because "The shooter will never stand on a wall."

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

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