Մաքսիմալ ընկերասեր զույգերը
Հարթության վրա տրված են իրարից տարբեր
y1 = y2։ Ձեր խնդիրն է, տրված n հատ զույգերի, որ ընկերասեր զույգերի քանակը լինի հնարավորինս մաքսիմալ։Մուտքային տվյալներ
Մուտքային տվյալների առաջին տողում տրված է մեկ ամբողջ թիվ՝
n։ Հաջորդ 2n տողերից յուրաքանչյուրում տրված են երկու ամբողջ թիվ` 2n կետերը իրարից տարբեր են։Ելքային տվյալներ
Ելքային տվյալների առաջին տողում անհրաժեշտ է արտածել մեկ ամբողջ թիվ՝ մաքսիմալ հնարավոր ընկերասեր զույգերի քանակը։ Հաջորդ
n տողերից յուրաքանչյուրում անհրաժեշտ է արտածել երկու ամբողջ թիվ՝ զույգերի ինդեքսները բաժանված բացատով։Օրինակ
Մուտք | Ելք |
2
1 0
1 1
1 2
2 1 | 2
1 3
2 4 |
3
0 0
2 1
3 1
1 2
2 2
3 3 | 2
6 3
4 5 |
Բացատրություն
Առաջին օրինակում կարող ենք կազմել առավելագույնը 2 ընկերասեր զույգեր.
(1, 0) և (1, 2), (1, 1) և (2, 1)։Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները,
- Ենթախնդիր 1 (10 միավոր)
, բոլոր կետերը ունեն կամ նույն x կորդինատը կամ նույն y կորդինատը,
- Ենթախնդիր 2 (20 միավոր)
, կամայական x-ի կամ y-ի համար, գոյություն ունեն ամենաշատը երկու կետեր
- Ենթախնդիր 3 (40 միավոր)
- Ենթախնդիր 4 (30 միավոր)
:
Constraints
Time limit: 0.6 seconds
Memory limit: 512 MB
Output limit: 2 MB