CSES - COCI 2007/2008 #2 - Results
Submission details
Task:Pravokutni
Sender:henrikaalto
Submission time:2019-07-31 15:17:38 +0300
Language:C++ (C++17)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED100
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.06 sdetails
#5ACCEPTED0.08 sdetails
#6ACCEPTED0.10 sdetails
#7ACCEPTED0.14 sdetails
#8ACCEPTED0.17 sdetails
#9ACCEPTED0.24 sdetails
#10ACCEPTED0.23 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:50:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for( int j = 0, k; j < rays.size(); j = k ) {
                          ~~^~~~~~~~~~~~~
input/code.cpp:54:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
          for( k = j; k < rays.size() && angle_eq( rays[j], rays[k] ); ++k ) 
                      ~~^~~~~~~~~~~~~
input/code.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf( "%d", &n );
    ~~~~~^~~~~~~~~~~~
input/code.cpp:26:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    for( int i = 0; i < n; ++i ) scanf( "%d%d", &x[i], &y[i] );
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Code

#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

#define MAX 1500

struct ray {
   long long dx, dy;
   int quadrant;

   void rotate90() {
      long long tmp = dx; dx = dy; dy = -tmp;
      quadrant = (quadrant+1)%4;
   }
};
bool angle_lt ( const ray &A, const ray &B ) { return A.dy*B.dx <  B.dy*A.dx; }
bool angle_eq ( const ray &A, const ray &B ) { return A.dy*B.dx == B.dy*A.dx; }

int n;
int x[MAX], y[MAX];

int main( void ) {
   scanf( "%d", &n );
   for( int i = 0; i < n; ++i ) scanf( "%d%d", &x[i], &y[i] );

   int solution = 0;

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

      vector<ray> rays;

      for( int j = 0; j < n; ++j ) {
         if( i == j ) continue;

         ray R;
         R.quadrant = 0;
         R.dx = x[j]-x[i];
         R.dy = y[j]-y[i];

         while( !(R.dx > 0 && R.dy >= 0) ) R.rotate90();
         
         rays.push_back( R );
      }

      sort( rays.begin(), rays.end(), angle_lt ); 
      
      int count[4];
      for( int j = 0, k; j < rays.size(); j = k ) {

         count[0] = count[1] = count[2] = count[3] = 0;

         for( k = j; k < rays.size() && angle_eq( rays[j], rays[k] ); ++k ) 
            ++count[rays[k].quadrant];
         
         solution += count[0] * count[1];
         solution += count[1] * count[2];
         solution += count[2] * count[3];
         solution += count[3] * count[0];
      }
   }

   printf( "%d\n", solution );

   return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
11
2 1
7 7
0 0
-8 -7
...

correct output
8

user output
8

Test 2

Verdict: ACCEPTED

input
77
25 -19
-13 -11
-2 -24
-19 4
...

correct output
8082

user output
8082

Test 3

Verdict: ACCEPTED

input
219
2 -8
859 -3283
33 -49
2 -45
...

correct output
2533

user output
2533

Test 4

Verdict: ACCEPTED

input
751
-841 1308
-1603 -1143
657 -330
1565 1551
...

correct output
180

user output
180

Test 5

Verdict: ACCEPTED

input
887
-318 -111
-51 -42
-60 30
0 15
...

correct output
656682

user output
656682

Test 6

Verdict: ACCEPTED

input
979
-19978 14584
-19978 13600
22840 -19949
-19712 14218
...

correct output
217863

user output
217863

Test 7

Verdict: ACCEPTED

input
1240
509503063 -256406432
-487207177 245187456
-487207659 245185046
-392411792 -779758123
...

correct output
261035

user output
261035

Test 8

Verdict: ACCEPTED

input
1419
908609234 -961461577
908607806 -961461577
908608142 -961460058
908607491 -961461577
...

correct output
471204

user output
471204

Test 9

Verdict: ACCEPTED

input
1494
17337298 165736671
41562836 397321778
286305326 -29949683
392177969 -41024755
...

correct output
2984

user output
2984

Test 10

Verdict: ACCEPTED

input
1500
99601355 -35091687
142757373 -376358953
-233911476 -88725398
-3360747 -162507391
...

correct output
192311

user output
192311