아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Štapovi

시간 제한2초메모리 제한1024 MB

요약
빨간 가로 선분과 파란 세로 선분 중 서로 만나는 쌍의 개수를 센다. 끝점이 닿는 경우도 교차로 본다.
난이도

보통10점 중 6점

유형
정렬, 투 포인터, 누적 합
정답자
아직 제출이 없습니다

문제

Na podu Mirkove sobe leži NN štapova, neki su crvene, a neki plave boje. Pod možemo prikazati kao koordinatnu ravninu u kojoj se oba kraja svakog štapa nalaze u različitim cjelobrojnim točkama. Crveni štapovi paralelni su s xx-osi, dok su plavi paralelni s yy-osi. Štapovi iste boje međusobno se ne sijeku niti dodiruju.

Mirka zanima ukupan broj sjecišta štapova, tj. broj parova crvenih i plavih štapova koji se međusobno sijeku. Štapovi se sijeku čak i ako se samo dodiruju, tj. ako imaju zajedničke krajeve ili kraj jednog štapa leži na drugom štapu.

Prikazan je raspored štapova is prvog probnog primjera:

Kao što vidimo, ukupan broj sjecišta je 3.

입력

U prvom je retku prirodan broj NN (1≤N≤500,0001 ≤ N ≤ 500\\,000), broj iz teksta zadatka.

Slijedi NN puta po četiri cijela broja X_1,Y_1,X_2,Y_2X\_1, Y\_1, X\_2, Y\_2, (0≤X_1,Y_1,X_2,Y_2≤1060 ≤ X\_1, Y\_1, X\_2, Y\_2 ≤ 10^6) koji redom predstavljaju x i y koordinatu prvog odnosno drugog kraja štapa.

Štapovi su dani u proizvoljnom poretku.

출력

Ispiši ukupan broj sjecišta štapova.

힌트

Opis prvog primjera: Vidi sliku iz teksta zadatka.

예제3

  1. 예제 1

    입력
    5
2 5 5 5
2 5 2 1
4 4 4 6
6 2 2 2
6 5 6 3
    예상 출력
    3

  2. 예제 2

    입력
    3
6 0 6 1000000
8 1000000 8 0
1 2 10 2
    예상 출력
    2

  3. 예제 3

    입력
    2
1 1 1 2
3 3 3 4
    예상 출력
    0