Rectangles Counting

Are all points different ?

I doubt that.

I hope it is not against the rules to clarify that my accepted solution treats (1,0) (1,0) (2,0) (2,0) as a rectangle.

@admin

I think the input set should have had N distinct points.

how is the answer for test case 3 ?

i can see only one rectangle (7,1),(7,5),(3,5),(3,1).

(7,1),(7,5),(1,1),(1,5)  is another one.

ohh.sorry....

got confused...

Do we really need to end input with 0?

oops sorry got it several test cases!!

@Admins: Please Correct the test cases: (1,0) (1,0) (2,0) (2,0) this kind of points are definitely not rectangles :|

@admin

plz ans above questions asked.

The first five words of the problem statement are:

Given N separate integer points

@Stephen , Thats why everyone is puzzled.

The statement does not match with actual data.(As far as I think.)

why isnt O(nlogn) sloution passing? Its getting timed out. Is there a more efficient way to solve this problem? Need help on this one please.

@  stephen:::can answer be zero also??...suppose if the coordinates are (2,0),(3,1),(4,1),(1,5)  no rectangle are formed ...that means answer will be null...so plz reply...i m vry close

Yes the answer can be zero ...

My solution is giving TLE just for reading the inputs. If time limits are so strict then how to process the points and get answer.I wonder how  so many correct answers came for this problem??

Will be interesting to see solutions after contest is over.

Is (1,0) (1,0) (2,0) (2,0) case still valid as a rectangle? My program counts it as a good answer at the moment. My program gives good answer on example input. Maybe I have an error somewhere else, but first I need to know if this case if valid or not?

what does source limit 50000 means? Is it a memory restriction in bytes?

what does source limit 50000 means? Is it a memory restriction in bytes?

I agree to Manohar Singh... I too just tried reading the input!! and it gives me TLE ... :-o ... time limits always frustrates me on Codechef... :-(

can anyone give me a sample input for 1 test cases?

IS

6
7 1
3 5
3 1
1 5
1 1
7 5
0
4
1 1
1 2
0 1
0 2
0

a valid input?

@Nitin .. it's mentioned.. N lines follow, each containing a pair of integers!!! so.. it can be...

Why are the solutions being rejudged?

There were some test cases that were not matching the problem statement. We modified the test and thus solutions are being rejudged.

will you please give us some more test cases to work out!!

does runtime error comes in any other way excpet that mentioned in FAQ??

can this be a testcase?

4
3 4
3 3
3 4
3 3
0

@cco

no man  "there is no any three of them sharing a same X-coordinate"

thanks RIJIN

can a square formed from 4 points be counted...

or strictly only quadrangles in which length is greater than height(rectangles) needs to be counted.

please reply..

@ccptrain, Square should be counted. Squae is also a rectangle.

# admin : what if the input contains 3 points with same x-coordinate shout it stop executoin of the program i.e. exit or should take another set of inputs ?

@Sandip .. if problem statement states that there would be no such case.. then.. believe them.. it won't be there.. :-)

@Above all who concluded , its giving TLE while taking input

u r wrong!

i m getting time limit exceeding in my O(n^2) algo..............is there any shorter method for this?

TLE for my code plz suggest what to do..

#include <stdio.h>

#include <algorithm>

#include <vector>

#include <map>

using namespace std;

#define PB push_back

#define MP make_pair

typedef pair<int,int> PII;

int main()

{

stdio_base::sync_with_stdio(0);

int n;

printf("%d",n);

while(n)

{

vector<PII> tab;

for(int i = 0;i < n;++i)

{

int a, b;cin >> a >> b;

tab.PB(MP(a, b));

}

if(n < 4) cout << "0n";

else

{

sort(tab.begin(), tab.end());

vector<PII> nowe;

if(tab[0].first == tab[1].first) nowe.PB(tab[0]);

for(int i = 1;i < n - 1;++i)

{

if(tab[i].first == tab[i - 1].first || tab[i].first == tab[i + 1].first) nowe.PB(tab[i]);

}

if(tab[n - 1].first == tab[n - 2].first) nowe.PB(tab[n - 1]);

map<PII,int> m;

for(unsigned int i = 0;i < nowe.size();i += 2)

{

int y1 = min(nowe[i].second, nowe[i + 1].second);

int y2 = max(nowe[i].second, nowe[i + 1].second);

++m[MP(y1, y2)];

}

map<PII,int>::iterator it;

unsigned long long int w = 0;

for(it = m.begin();it != m.end();++it)

{

int x = (*it).second;

w += ((long long)x * (x - 1)) / 2;

}

printf("%d ",w /n);

}

printf("%d",n);

}

return 0;

}