-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathCRESC132.SIF
4640 lines (3227 loc) · 99.9 KB
/
CRESC132.SIF
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
***************************
* SET UP THE INITIAL DATA *
***************************
NAME CRESC132
* Problem :
* *********
* This problem consists in finding the crescent of smallest area containing
* a set of points given in the plane. This problem arises as a subproblem
* in pattern recognition and has been suggested by J.P. Rasson. It
* originates in the detection of "salt domes" (with the potential presence of
* oil pockets!) from geological data.
* The problem is not convex.
* A crescent is defined as follows. Assume one has two circles of center
* C1 and C2 and of radii r1 and r2 respectively. Assume furthermore that
* r1 >= r2 and that C2 is within C1. Assume finally that the distance from
* C1 to C2 is >= r1 - r2. Then the crescent is the part of the plane
* contained in circle 2 but not in circle 1.
* In order to preserve feasibility at all stages (ensuring that the
* crescent exists and that its area can be computed), the following
* parametrization is used:
* ( C2x, C2y ) = ( C1x, C1y ) + a * d * ( cos(t), sin(t) )
* r1 = a * d + r
* r2 = ( a + 1 ) * d + r
* with the bounds
* a >= 1, 0 <= t <= 2 * pi, r2 >= 0 , 0 <= d <= 1.
* SIF input: Ph. Toint, June 1993.
* classification OOR2-MY-6-2654
* number of points to be included in the crescent.
* the number of constraints is 2*NP
IE NP 1327
* data points
RE X1 0.54160
RE Y1 0.21689
RE X2 0.62933
RE Y2 0.48206
RE X3 0.50333
RE Y3 0.51776
RE X4 0.48624
RE Y4 0.50858
RE X5 0.66324
RE Y5 0.02686
RE X6 0.21786
RE Y6 0.95581
RE X7 0.46863
RE Y7 0.51147
RE X8 0.76315
RE Y8 0.04459
RE X9 0.51715
RE Y9 0.82867
RE X10 0.85770
RE Y10 0.46561
RE X11 0.96133
RE Y11 0.01163
RE X12 0.24216
RE Y12 0.87390
RE X13 0.69666
RE Y13 0.01865
RE X14 0.21701
RE Y14 0.87833
RE X15 0.71820
RE Y15 0.60071
RE X16 0.82928
RE Y16 0.25519
RE X17 0.54565
RE Y17 0.61316
RE X18 0.37076
RE Y18 0.88333
RE X19 0.62225
RE Y19 0.23712
RE X20 0.58820
RE Y20 0.02582
RE X21 0.52753
RE Y21 0.51657
RE X22 0.55716
RE Y22 0.12753
RE X23 0.73499
RE Y23 0.21698
RE X24 0.51770
RE Y24 0.41684
RE X25 0.66418
RE Y25 0.36417
RE X26 0.92169
RE Y26 0.17413
RE X27 0.55020
RE Y27 0.53085
RE X28 0.83667
RE Y28 0.31583
RE X29 0.26065
RE Y29 0.80185
RE X30 0.25485
RE Y30 0.96469
RE X31 0.47543
RE Y31 0.31760
RE X32 0.49014
RE Y32 0.33707
RE X33 0.72913
RE Y33 0.29944
RE X34 0.47360
RE Y34 0.81223
RE X35 0.34262
RE Y35 0.85269
RE X36 0.34497
RE Y36 0.77600
RE X37 0.59692
RE Y37 0.58630
RE X38 0.51666
RE Y38 0.61298
RE X39 0.73492
RE Y39 0.41916
RE X40 0.43579
RE Y40 0.48877
RE X41 0.51633
RE Y41 0.64871
RE X42 0.85379
RE Y42 0.10593
RE X43 0.58545
RE Y43 0.36688
RE X44 0.35999
RE Y44 0.75226
RE X45 0.14532
RE Y45 0.93146
RE X46 0.39978
RE Y46 0.54541
RE X47 0.48816
RE Y47 0.62222
RE X48 0.50375
RE Y48 0.82770
RE X49 0.79398
RE Y49 0.26215
RE X50 0.97574
RE Y50 0.04956
RE X51 0.92514
RE Y51 0.34409
RE X52 0.62531
RE Y52 0.43701
RE X53 0.96393
RE Y53 0.06812
RE X54 0.46826
RE Y54 0.76263
RE X55 0.45483
RE Y55 0.57288
RE X56 0.78513
RE Y56 0.05612
RE X57 0.83997
RE Y57 0.42236
RE X58 0.36212
RE Y58 0.91183
RE X59 0.91953
RE Y59 0.02765
RE X60 0.88242
RE Y60 0.36975
RE X61 0.85196
RE Y61 0.26825
RE X62 0.54974
RE Y62 0.64960
RE X63 0.76907
RE Y63 0.58398
RE X64 0.39380
RE Y64 0.91663
RE X65 0.85049
RE Y65 0.44461
RE X66 0.54111
RE Y66 0.53983
RE X67 0.39258
RE Y67 0.59894
RE X68 0.85501
RE Y68 0.03320
RE X69 0.43997
RE Y69 0.75696
RE X70 0.46423
RE Y70 0.64041
RE X71 0.42355
RE Y71 0.78772
RE X72 0.59024
RE Y72 0.49734
RE X73 0.22876
RE Y73 0.86469
RE X74 0.13995
RE Y74 0.90378
RE X75 0.67743
RE Y75 0.54556
RE X76 0.21875
RE Y76 0.87143
RE X77 0.25156
RE Y77 0.87564
RE X78 0.64081
RE Y78 0.45212
RE X79 0.68665
RE Y79 0.47601
RE X80 0.93658
RE Y80 0.34573
RE X81 0.09988
RE Y81 0.98404
RE X82 0.72522
RE Y82 0.66394
RE X83 0.78592
RE Y83 0.01431
RE X84 0.61807
RE Y84 0.78540
RE X85 0.68079
RE Y85 0.01340
RE X86 0.21017
RE Y86 0.95984
RE X87 0.75742
RE Y87 0.19827
RE X88 0.68811
RE Y88 0.21606
RE X89 0.65530
RE Y89 0.64539
RE X90 0.75302
RE Y90 0.59900
RE X91 0.36484
RE Y91 0.71927
RE X92 0.90869
RE Y92 0.25992
RE X93 0.18900
RE Y93 0.84836
RE X94 0.75620
RE Y94 0.07120
RE X95 0.59030
RE Y95 0.00677
RE X96 0.43054
RE Y96 0.87900
RE X97 0.77567
RE Y97 0.51868
RE X98 0.21884
RE Y98 0.93915
RE X99 0.48782
RE Y99 0.67944
RE X100 0.18924
RE Y100 0.95276
RE X101 0.03528
RE Y101 0.99069
RE X102 0.40201
RE Y102 0.75757
RE X103 0.65097
RE Y103 0.57840
RE X104 0.97253
RE Y104 0.16208
RE X105 0.67447
RE Y105 0.01050
RE X106 0.72568
RE Y106 0.32721
RE X107 0.43781
RE Y107 0.42691
RE X108 0.69910
RE Y108 0.67697
RE X109 0.21890
RE Y109 0.94821
RE X110 0.33804
RE Y110 0.80945
RE X111 0.51605
RE Y111 0.66125
RE X112 0.72189
RE Y112 0.63153
RE X113 0.49237
RE Y113 0.77936
RE X114 0.88904
RE Y114 0.25363
RE X115 0.60083
RE Y115 0.17761
RE X116 0.47513
RE Y116 0.27713
RE X117 0.58395
RE Y117 0.44702
RE X118 0.38113
RE Y118 0.56219
RE X119 0.51871
RE Y119 0.58185
RE X120 0.50391
RE Y120 0.25760
RE X121 0.24042
RE Y121 0.96912
RE X122 0.54324
RE Y122 0.39221
RE X123 0.33105
RE Y123 0.67093
RE X124 0.54419
RE Y124 0.59283
RE X125 0.59348
RE Y125 0.53360
RE X126 0.86346
RE Y126 0.45697
RE X127 0.28952
RE Y127 0.79517
RE X128 0.42371
RE Y128 0.78040
RE X129 0.58020
RE Y129 0.16278
RE X130 0.22000
RE Y130 0.82242
RE X131 0.50696
RE Y131 0.00757
RE X132 0.50116
RE Y132 0.58984
RE X133 0.15094
RE Y133 0.91092
RE X134 0.33585
RE Y134 0.89172
RE X135 0.57849
RE Y135 0.41049
RE X136 0.69128
RE Y136 0.37247
RE X137 0.88251
RE Y137 0.18231
RE X138 0.53369
RE Y138 0.73105
RE X139 0.97183
RE Y139 0.07727
RE X140 0.93967
RE Y140 0.07495
RE X141 0.56335
RE Y141 0.43082
RE X142 0.33444
RE Y142 0.66733
RE X143 0.42215
RE Y143 0.52017
RE X144 0.54404
RE Y144 0.41818
RE X145 0.73151
RE Y145 0.62259
RE X146 0.57291
RE Y146 0.59891
RE X147 0.34119
RE Y147 0.81439
RE X148 0.57352
RE Y148 0.02161
RE X149 0.56900
RE Y149 0.57785
RE X150 0.35562
RE Y150 0.91843
RE X151 0.90332
RE Y151 0.24686
RE X152 0.64700
RE Y152 0.01022
RE X153 0.56223
RE Y153 0.41599
RE X154 0.66129
RE Y154 0.50061
RE X155 0.52634
RE Y155 0.84552
RE X156 0.47458
RE Y156 0.48874
RE X157 0.62076
RE Y157 0.39838
RE X158 0.78284
RE Y158 0.04150
RE X159 0.32205
RE Y159 0.92969
RE X160 0.47742
RE Y160 0.37839
RE X161 0.52524
RE Y161 0.47382
RE X162 0.31210
RE Y162 0.75739
RE X163 0.93207
RE Y163 0.18329
RE X164 0.87024
RE Y164 0.18054
RE X165 0.93704
RE Y165 0.13342
RE X166 0.68188
RE Y166 0.10446
RE X167 0.46976
RE Y167 0.83115
RE X168 0.62616
RE Y168 0.32852
RE X169 0.76010
RE Y169 0.14313
RE X170 0.64270
RE Y170 0.12137
RE X171 0.34268
RE Y171 0.64639
RE X172 0.70529
RE Y172 0.39319
RE X173 0.77863
RE Y173 0.46478
RE X174 0.64081
RE Y174 0.01242
RE X175 0.92673
RE Y175 0.15961
RE X176 0.47821
RE Y176 0.23303
RE X177 0.60547
RE Y177 0.67947
RE X178 0.81549
RE Y178 0.46967
RE X179 0.52353
RE Y179 0.75720
RE X180 0.61310
RE Y180 0.31509
RE X181 0.83630
RE Y181 0.32532
RE X182 0.92862
RE Y182 0.32489
RE X183 0.34805
RE Y183 0.80762
RE X184 0.86102
RE Y184 0.47995
RE X185 0.46542
RE Y185 0.55936
RE X186 0.58337
RE Y186 0.06308
RE X187 0.20514
RE Y187 0.86145
RE X188 0.41199
RE Y188 0.82947
RE X189 0.31586
RE Y189 0.85519
RE X190 0.70135
RE Y190 0.39838
RE X191 0.24005
RE Y191 0.78214
RE X192 0.49234
RE Y192 0.42078
RE X193 0.82001
RE Y193 0.22183
RE X194 0.94150
RE Y194 0.28516
RE X195 0.42944
RE Y195 0.71655
RE X196 0.65652
RE Y196 0.21140
RE X197 0.12097
RE Y197 0.97995
RE X198 0.48206
RE Y198 0.45773
RE X199 0.81302
RE Y199 0.03683
RE X200 0.84705
RE Y200 0.11893
RE X201 0.74316
RE Y201 0.49753
RE X202 0.33060
RE Y202 0.86777
RE X203 0.72208
RE Y203 0.27747
RE X204 0.55374
RE Y204 0.02942
RE X205 0.44366
RE Y205 0.82263
RE X206 0.97662
RE Y206 0.03012
RE X207 0.45923
RE Y207 0.88522
RE X208 0.25970
RE Y208 0.77371
RE X209 0.12183
RE Y209 0.97940
RE X210 0.33804
RE Y210 0.77026
RE X211 0.66983
RE Y211 0.22232
RE X212 0.43222
RE Y212 0.63696
RE X213 0.34082
RE Y213 0.79529
RE X214 0.99319
RE Y214 0.04025
RE X215 0.57758
RE Y215 0.12170
RE X216 0.53134
RE Y216 0.42120
RE X217 0.95584
RE Y217 0.05212
RE X218 0.92670
RE Y218 0.35281
RE X219 0.69833
RE Y219 0.59177
RE X220 0.65747
RE Y220 0.03613
RE X221 0.73309
RE Y221 0.64996
RE X222 0.75101
RE Y222 0.29767
RE X223 0.93280
RE Y223 0.25522
RE X224 0.99454
RE Y224 0.08145
RE X225 0.50208
RE Y225 0.59604
RE X226 0.90039
RE Y226 0.35529
RE X227 0.65378
RE Y227 0.55804
RE X228 0.93179
RE Y228 0.07727
RE X229 0.33554
RE Y229 0.63162
RE X230 0.06445
RE Y230 0.95352
RE X231 0.22940
RE Y231 0.87817
RE X232 0.73669
RE Y232 0.41718
RE X233 0.41214
RE Y233 0.71335
RE X234 0.89413
RE Y234 0.23096
RE X235 0.77637
RE Y235 0.02972
RE X236 0.54623
RE Y236 0.06158
RE X237 0.39355
RE Y237 0.57956
RE X238 0.64096
RE Y238 0.24631
RE X239 0.51059
RE Y239 0.16669
RE X240 0.51382
RE Y240 0.73846
RE X241 0.31033
RE Y241 0.74915
RE X242 0.68341
RE Y242 0.52881
RE X243 0.11908
RE Y243 0.92743
RE X244 0.50427
RE Y244 0.71805
RE X245 0.58548
RE Y245 0.33893
RE X246 0.46756
RE Y246 0.72998
RE X247 0.87164
RE Y247 0.36920
RE X248 0.86911
RE Y248 0.00165
RE X249 0.89169
RE Y249 0.40952
RE X250 0.63565
RE Y250 0.76678
RE X251 0.66882
RE Y251 0.27405
RE X252 0.41690
RE Y252 0.66330
RE X253 0.59067
RE Y253 0.33987
RE X254 0.89056
RE Y254 0.04504
RE X255 0.75345
RE Y255 0.62006
RE X256 0.25153
RE Y256 0.92618
RE X257 0.63541
RE Y257 0.59979
RE X258 0.63483
RE Y258 0.57635
RE X259 0.45010
RE Y259 0.55402
RE X260 0.69711
RE Y260 0.61609
RE X261 0.45349
RE Y261 0.34201
RE X262 0.54324
RE Y262 0.04031
RE X263 0.59848
RE Y263 0.13495
RE X264 0.55389
RE Y264 0.02487
RE X265 0.90610
RE Y265 0.40311
RE X266 0.50082
RE Y266 0.64304
RE X267 0.33566
RE Y267 0.66153
RE X268 0.46609
RE Y268 0.49854
RE X269 0.72919
RE Y269 0.66486
RE X270 0.83340
RE Y270 0.38867
RE X271 0.64279
RE Y271 0.64520
RE X272 0.25946
RE Y272 0.81049
RE X273 0.39304
RE Y273 0.74905
RE X274 0.56351
RE Y274 0.20966
RE X275 0.72031
RE Y275 0.03473
RE X276 0.80328
RE Y276 0.44711
RE X277 0.73618
RE Y277 0.54666
RE X278 0.90247
RE Y278 0.02286
RE X279 0.55826
RE Y279 0.20261
RE X280 0.70178
RE Y280 0.22476
RE X281 0.59622
RE Y281 0.36343
RE X282 0.66428
RE Y282 0.18793
RE X283 0.79526
RE Y283 0.10822
RE X284 0.53320
RE Y284 0.71539
RE X285 0.65277
RE Y285 0.71875
RE X286 0.56229
RE Y286 0.47888
RE X287 0.23163
RE Y287 0.85419
RE X288 0.63864
RE Y288 0.00488
RE X289 0.64667
RE Y289 0.70325
RE X290 0.84741
RE Y290 0.13922
RE X291 0.61911
RE Y291 0.62119
RE X292 0.21463
RE Y292 0.82617
RE X293 0.65744
RE Y293 0.47968
RE X294 0.51706
RE Y294 0.27188
RE X295 0.67123
RE Y295 0.44702
RE X296 0.81668
RE Y296 0.38797
RE X297 0.74628
RE Y297 0.33319
RE X298 0.59595
RE Y298 0.27536
RE X299 0.97781
RE Y299 0.04794
RE X300 0.25568
RE Y300 0.94196
RE X301 0.91107
RE Y301 0.04950
RE X302 0.41547
RE Y302 0.61688
RE X303 0.55994
RE Y303 0.11569
RE X304 0.22931
RE Y304 0.93680
RE X305 0.68576
RE Y305 0.15897
RE X306 0.57767
RE Y306 0.52255
RE X307 0.44525
RE Y307 0.54337
RE X308 0.56335
RE Y308 0.02325
RE X309 0.68704
RE Y309 0.71631
RE X310 0.49823
RE Y310 0.35077
RE X311 0.32773
RE Y311 0.68896
RE X312 0.66049
RE Y312 0.30328
RE X313 0.99130
RE Y313 0.12570
RE X314 0.65134
RE Y314 0.38467
RE X315 0.84610
RE Y315 0.24750
RE X316 0.84229
RE Y316 0.21014
RE X317 0.50336
RE Y317 0.58826
RE X318 0.60065