Problem Statement
You are given the coordinates of N points on the 2-dimensional plane. No two points are coincident and no three are collinear. Find the number of pairs of intersecting line segments whose endpoints are among the given points. The line segments within each pair must not share any common endpoints.
For example, if the given points are {(1, 4), (2, 1), (0, 0), (1, 3) and (2, 4)}, then there are three valid pairs of intersecting line segments as shown in the pictures below.
The king wants you to write a program to solve the above problem so that the answer given by the prince can be checked. The rth point is (xr, yr). The x-coordinates of the points can be generated by using the following recursive definition:
x1 = xFirst, and
xi = (xi-1*xProd + xAdd) mod xMod, for 2 ≤ i ≤ N
(Note that (xi-1*xProd + xAdd) may overflow 32-bit integers)
The values of yr are defined similarly using yFirst, yAdd, yProd and yMod.Definition
- Class:
- LineSegments
- Method:
- intersections
- Parameters:
- int, int, int, int, int, int, int, int, int
- Returns:
- long
- Method signature:
- long intersections(int N, int xFirst, int xAdd, int xProd, int xMod, int yFirst, int yAdd, int yProd, int yMod)
- (be sure your method is public)
Constraints
- N will be between 2 and 1200, inclusive.
- xMod and yMod will be between 1 and 1000000, inclusive.
- xFirst, xAdd and xProd will be between 0 and (xMod-1), inclusive.
- yFirst, yAdd and yProd will be between 0 and (yMod-1), inclusive.
- The values of the arguments will be such that among the N generated points (using the above definition), no two points will be coincident and no three will be collinear.
Examples
6
101080
5500
396324
412247
58495
46559
1680
81684
Returns: 10
5
88874
396279
597237
880235
258031
214893
320708
930580
Returns: 3
9
267352
11896
307137
447945
375427
194282
41875
490478
Returns: 80
7
217366
166352
213623
304880
418434
343792
355233
554631
Returns: 25
2
286304
478063
335016
606832
186861
55432
200484
233630
Returns: 0
2
18466
100835
10728
163888
887627
80657
143821
917656
Returns: 0
4
496274
263388
654306
671869
570463
535598
556861
618367
Returns: 1
9
69615
513423
532548
534611
294342
463210
249558
471264
Returns: 92
5
180916
83072
518673
859401
32973
65582
38972
90681
Returns: 5
10
104892
64230
326546
917720
242644
230975
312843
496349
Returns: 162
31
274616
314585
223942
823330
28930
38505
45239
50471
Returns: 20891
152
21846
78225
32086
98638
75455
28999
28325
98368
Returns: 15128313
481
25278
67539
91119
92629
110798
563222
131740
724180
Returns: 1534859838
223
22225
153571
114803
223684
374367
37193
425745
518257
Returns: 69521195
758
305093
91978
354756
475884
436566
581254
888953
942710
Returns: 9503053716
213
615209
466064
622047
781424
31019
82342
150649
821948
Returns: 57931217
599
115886
232632
107519
286607
212866
126756
164397
310173
Returns: 3667059605
651
139515
220300
53277
234999
110814
598196
396000
750463
Returns: 5119162826
100
201589
471082
599341
831642
433024
189298
315570
461507
Returns: 2663094
421
156483
224344
236742
633008
32937
95346
78531
170834
Returns: 884593069
63
195017
137250
266817
365963
961501
255982
519173
968155
Returns: 424051
780
4673
394817
262857
715269
329199
335098
216959
382575
Returns: 10726877970
169
171370
3728
647283
909437
50423
142704
223455
361428
Returns: 22623752
728
529626
419600
12350
604172
850111
146092
410373
880499
Returns: 8031085057
125
265037
134919
660462
799358
29498
94631
96355
121312
Returns: 6782907
6
83202
336187
388872
415367
4126
85984
304968
802562
Returns: 9
139
546898
354267
647613
767747
176380
170481
285468
357831
Returns: 10318412
119
46255
572256
261017
741445
14833
314
14428
16129
Returns: 5507681
352
89314
555561
368967
642268
666162
647342
707504
836330
Returns: 435536688
87
16409
52217
8185
71929
16314
13481
7031
27044
Returns: 1511179
121
907311
319993
381460
919184
667500
57792
628539
891005
Returns: 5851734
514
648498
790552
250703
917409
149113
620209
32418
722360
Returns: 1993765074
87
149680
160032
136739
686731
154193
138592
92079
201770
Returns: 1528955
295
922842
105132
142975
990946
989645
938262
712650
994968
Returns: 219118919
371
131373
114797
497705
771816
580936
528441
116536
849403
Returns: 539589536
728
32030
608625
471887
625981
80688
37185
59053
94366
Returns: 8076268802
313
54966
34075
60550
108998
622122
205581
823884
829355
Returns: 273941518
314
60
12770
2030
22371
36552
44078
131775
156643
Returns: 279545593
272
167855
22573
214030
401243
691079
590017
418117
791688
Returns: 154726639
520
351626
447199
275552
659283
690524
570888
210876
733603
Returns: 2085539499
84
78176
110396
4765
191199
7994
45391
56473
60344
Returns: 1334483
236
494193
82188
391433
513206
345856
254023
18554
482012
Returns: 86170998
833
84890
38377
3124
90996
87182
218740
227570
643759
Returns: 13762842690
526
3015
533
16915
27792
188904
653638
628948
740958
Returns: 2167414208
802
4062
5373
7199
11303
137808
552594
835523
858726
Returns: 11984396107
93
20012
359827
365581
680894
810858
805509
291655
934944
Returns: 2035607
137
34833
142811
291200
637958
995205
503969
479159
995318
Returns: 9807518
849
214050
328657
415892
507414
178030
5196
76139
288193
Returns: 14881463054
867
101077
222655
42326
232766
42080
137401
86196
447165
Returns: 16214848016
142
9381
421296
315491
780677
345491
130800
36627
391394
Returns: 11447371
3
335937
661082
850967
997843
166090
180476
750
191767
Returns: 0
738
185024
57948
248391
589452
225217
631271
383907
777363
Returns: 8546448890
886
297863
356774
595132
764564
400852
144688
576390
904987
Returns: 17819499953
394
34199
180729
624908
919368
108724
75496
89988
600933
Returns: 680589771
398
797685
293491
158556
942367
213657
441484
144512
597919
Returns: 714237061
983
566878
289497
581182
595528
454349
200146
269094
600875
Returns: 26938374549
588
329001
166696
505237
680496
131459
53683
82424
183005
Returns: 3429721339
23
301785
76073
539642
785368
234578
635763
467331
769664
Returns: 5873
953
144775
156435
18184
336892
219848
102189
24191
488357
Returns: 23551003044
910
116522
3290
98683
365228
484347
255151
490781
547688
Returns: 19768741585
786
111742
4367
792700
921861
98399
995
195885
280220
Returns: 11000773416
569
51068
682553
235371
948726
605602
233033
876126
878448
Returns: 2987667310
628
178243
97380
657131
694984
668201
735494
583197
823037
Returns: 4413929336
51
23582
127059
570876
626114
624290
701408
100693
719001
Returns: 169762
6
190164
117049
286734
584955
303499
194650
113782
571623
Returns: 8
824
917102
691013
463457
942665
35831
33621
24619
58172
Returns: 13387693475
110
161678
138323
174404
207947
134997
669350
771339
889041
Returns: 4047110
824
98567
113202
140815
159441
216235
9770
210386
338955
Returns: 13213536219
927
28399
49547
47144
608508
473376
143634
377553
587410
Returns: 21003795363
953
122100
78567
124256
372831
11240
204717
360980
630918
Returns: 23837495608
1000
34885
196702
226508
243868
518704
780979
148741
825728
Returns: 28826404174
1000
104107
284589
611779
817829
70637
172055
73485
271794
Returns: 28602781987
1000
50362
7153
23096
908585
492863
201224
589441
976565
Returns: 28755934660
1000
107438
5238
267291
358715
199943
350880
345843
735169
Returns: 28638964569
1000
166192
184833
129608
265832
38161
126444
72901
553961
Returns: 28689410060
1000
226094
126818
128673
324129
292451
561585
30353
638709
Returns: 28779421854
1000
40920
536517
274043
638016
506946
90628
707046
711890
Returns: 28544075777
1000
235163
756763
77839
835014
631022
32862
793987
924278
Returns: 28912413234
1000
78896
264135
470437
663895
358417
604272
312
715573
Returns: 28910635637
1000
215657
553897
915611
930784
193666
323425
130393
654599
Returns: 28696823451
4
4
3
1
5
1
1
1
3
Returns: 0
The points are (4, 1), (2, 2), (0, 0) and (3, 1). No intersecting line segments.
4
1
1
1
2
4
1
1
5
Returns: 1
4
1
1
1
2
3
3
1
4
Returns: 1
4
1
2
1
3
1
1
1
2
Returns: 1
The points are (1, 1), (0, 0), (2, 1) and (1, 0). Line segment {(0, 0), (2, 1)} intersects with line segment {(1, 1), (1, 0)}.
5
1
1
1
3
4
3
2
5
Returns: 3
The example in the problem statement.
5
1
4
1
5
4
1
3
5
Returns: 3
5
3
1
3
5
1
2
1
3
Returns: 3
5
1
2
1
3
4
3
1
5
Returns: 3
6
1
3
1
5
1
2
1
3
Returns: 11
6
2
3
3
5
2
1
1
3
Returns: 15
6
215657
553897
915611
930784
193666
323425
130393
654599
Returns: 15
Make sure you take care of overflow.
1104
164249
297047
193601
485551
705892
418679
597851
804901
Returns: 42554704576
1042
108572
94474
418494
423498
768963
496477
289235
835276
Returns: 34031334086
1112
745871
614191
507128
750188
172236
67700
47667
173420
Returns: 43991854370
1008
809049
442733
763982
891409
363464
225921
205430
440887
Returns: 29570933808
1059
138053
348729
313407
467794
130410
244183
83360
618162
Returns: 36420890336
1171
96464
336449
450559
476834
204606
579838
82252
589905
Returns: 54437994930
1116
37269
43996
348287
367519
131204
129723
128294
336238
Returns: 44684598514
1058
52759
32834
78935
106797
135666
649118
755745
901658
Returns: 35506824644
1189
213439
106109
118135
254847
335820
400057
404291
877131
Returns: 57206204359
1137
101576
91217
284911
490155
365994
277574
284768
497632
Returns: 48315595666
1200
328670
637330
15826
760544
338223
556539
675329
845128
Returns: 59914831411
1200
323895
418003
74678
573734
81149
495212
13588
500241
Returns: 59627293424
1200
281528
321273
311544
408767
134127
82126
251878
405835
Returns: 60184421874
1200
184033
369158
641562
693993
129919
233928
64293
272134
Returns: 59961840933
1200
22624
63708
26833
111217
99287
279234
85710
356581
Returns: 59151049394
1200
441732
185492
261038
614348
260386
256630
104362
265312
Returns: 60432615385
1200
77795
438480
434038
449307
41036
1045
43716
150317
Returns: 59680059035
1200
201884
427202
684466
895458
299555
230700
393769
406209
Returns: 59287335023
1200
33210
135090
143817
149576
503902
115662
217700
679102
Returns: 59834281443
1200
20778
182538
5891
192979
83975
364021
132557
402926
Returns: 59505489981
95
58
114
80
121
618939
578153
716786
985631
Returns: 2153913
10
36
21
26
43
438635
383878
659282
999863
Returns: 150
30
2
20
12
47
25250
562052
97115
999288
Returns: 20057
77
50
27
31
59
169523
481850
198137
694346
Returns: 928435
61
15
20
72
83
455363
886872
213181
996739
Returns: 365989
10
40
42
50
62
94166
186551
157778
997293
Returns: 142
48
10
58
84
87
338077
400605
759595
978504
Returns: 135248
67
42
81
63
86
260614
912831
758334
1000000
Returns: 529706
144
42
119
36
199
287104
7144
61977
294805
Returns: 12182947
291
146
312
190
331
488402
376904
926433
999960
Returns: 203565334
453
493
263
581
601
511781
682209
9129
999979
Returns: 1204387405
1144
990
501
21
1669
695730
176097
375203
998147
Returns: 49549870753
67
260614
912831
758334
1000000
42
81
63
86
Returns: 529706
144
287104
7144
61977
294805
42
119
36
199
Returns: 12182947
291
488402
376904
926433
999960
146
312
190
331
Returns: 203565334
453
511781
682209
9129
999979
493
263
581
601
Returns: 1204387405
1144
695730
176097
375203
998147
990
501
21
1669
Returns: 49549870753