Poligoni interi#9441
Ingrid gestisce un negozio di poligoni in un paese lontano. Vende soltanto poligoni convessi con coordinate intere. I suoi clienti preferiscono i poligoni che possono essere tagliati in due metà in modo corretto: il taglio deve essere rettilineo, deve iniziare e terminare in vertici del poligono, ed entrambe le metà devono essere non vuote e avere area intera. Più sono i modi di tagliare correttamente un poligono, più il poligono è costoso.
Ad esempio, ci sono tre modi di tagliare correttamente il poligono di sinistra e due modi di tagliare quello di destra.
I poligoni del negozio sono sempre di ottima qualità, perciò l'attività è in espansione. Ora Ingrid ha bisogno di uno strumento automatico per determinare il numero di modi di tagliare correttamente un poligono. Questo è molto importante per il suo negozio, perché altrimenti passerebbe molto tempo a fissare i prezzi — provate a immaginare quanto tempo ci vorrebbe per prezzare un furgone di medie dimensioni pieno di poligoni. Potreste aiutare Ingrid scrivendo questo strumento per lei?
La prima riga contiene un numero intero n~(4 \le n \le 200000), il numero di vertici del poligono. Ognuna delle successive righe contiene le coordinate di un vertice: due numeri interi x_i e y_i~(-10^9 \le x_i, y_i \le 10^9).
Il poligono dato è convesso e i suoi vertici sono elencati nell'ordine di percorrenza.
Stampare un numero intero : il numero di modi di tagliare correttamente il poligono.
Esempio 1
Esempio 2