Problem B. 2. Counting rectangles
Input file name: standard input
Output file name: standard output
Time limit: 1 s
Memory limit: 1024 MB
Output file name: standard output
Time limit: 1 s
Memory limit: 1024 MB
Architektas rengia brėžinį begalinėje 2D plokštumoje. Jis nubraižo tikslius N stačiakampių kontūrus, kurių kraštinės lygiagrečios X ir Y ašims, o kampų koordinatės yra sveikieji skaičiai.
Svarbu: architektas braižo tik šių stačiakampių rėmus (kontūrus); vidiniai plotai nėra užpildomi. Kai atkarpos persidengia, jos susilieja į vieną bendrą atkarpą.
Jūsų užduotis — suskaičiuoti, kiek iš viso unikalių stačiakampių matoma galutiniame brėžinyje. Stačiakampis yra validus, jei bet kurie keturi jo kampai yra sujungti ištisinėmis, nenutrūkstamomis horizontaliomis ir vertikaliomis atkarpomis.
Svarbu: architektas braižo tik šių stačiakampių rėmus (kontūrus); vidiniai plotai nėra užpildomi. Kai atkarpos persidengia, jos susilieja į vieną bendrą atkarpą.
Jūsų užduotis — suskaičiuoti, kiek iš viso unikalių stačiakampių matoma galutiniame brėžinyje. Stačiakampis yra validus, jei bet kurie keturi jo kampai yra sujungti ištisinėmis, nenutrūkstamomis horizontaliomis ir vertikaliomis atkarpomis.
Input
Pirmoje eilutėje pateiktas vienas sveikasis skaičius N (1 \le N \le 100).
Tolesnėse N eilučių pateikta po keturis tarpais atskirtus sveikuosius skaičius x_1, y_1, x_2 ir y_2 (-100 \le x_1, y_1, x_2, y_2 \le 100; x_1 < x_2 ir y_1 > y_2), nurodančius atitinkamai viršutinio kairiojo ir apatinio dešiniojo kampo koordinates.
Tolesnėse N eilučių pateikta po keturis tarpais atskirtus sveikuosius skaičius x_1, y_1, x_2 ir y_2 (-100 \le x_1, y_1, x_2, y_2 \le 100; x_1 < x_2 ir y_1 > y_2), nurodančius atitinkamai viršutinio kairiojo ir apatinio dešiniojo kampo koordinates.
Output
Išveskite vieną sveikąjį skaičių: bendrą galutiniame brėžinyje matomų unikalių stačiakampių skaičių. Garantuojama, kad atsakymas bus mažesnis nei 10^6.
Examples
| standard input | standard output |
|---|---|
| 2 0 2 2 0 1 3 3 1 | 3 |
Note
Pavyzdžio paaiškinimas:
Du persidengiantys stačiakampiai gali sukurti papildomų stačiakampių tose vietose, kur jų kraštinės kertasi. Šiuo atveju du pradiniai stačiakampiai ir naujas stačiakampis, susiformavęs jų sankirtoje, iš viso sudaro 3 stačiakampius:
Du persidengiantys stačiakampiai gali sukurti papildomų stačiakampių tose vietose, kur jų kraštinės kertasi. Šiuo atveju du pradiniai stačiakampiai ir naujas stačiakampis, susiformavęs jų sankirtoje, iš viso sudaro 3 stačiakampius:
