Rezultati

Up. imeNalogaJezikRezultatČas oddaje
DROPTABLE-2017 Črte C++ 100/100OK 20. apr '17 @ 19:00

Test Točke Porabljen spomin Porabljen čas Status
#1 10/10 767,059 MiB 2,385 s OK
#2 10/10 767,063 MiB 2,318 s OK
#3 10/10 929,098 MiB 2,428 s OK
#4 10/10 820,355 MiB 5,229 s OK
#5 10/10 1252,852 MiB 9,005 s OK
#6 10/10 767,156 MiB 3,054 s OK
#7 10/10 767,152 MiB 3,231 s OK
#8 10/10 767,152 MiB 3,438 s OK
#9 10/10 767,148 MiB 3,627 s OK
#10 10/10 1501,145 MiB 5,661 s OK

Ocenjevani program (upm_line_seg.cpp):
//============================================================================
// Name        : upm_line_seg.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

int x[12000];
int y[12000];

unsigned short st[800000000];
int overflows[2500];
int top;
const int HUGE = 65535; //65535

int main() {
	memset(&st, 0, 800000000);
	top = 0;

	int N;
	cin >> N;

	if(N==1){
		cout << "0";
		return 0;
	}

	for(int i = 0; i < N; i++){
		cin >> x[i] >> y[i];
	}
	for(int a = 0; a < N-1; a++){
		int xa = x[a];
		int ya = y[a];
		for(int b = a+1; b < N; b++){
			int xaxb = xa - x[b];
			int yayb = ya - y[b];
			int keri = xaxb*xaxb+yayb*yayb;
			if(st[keri]==HUGE){
				st[keri] = 0;
				overflows[top] = keri;
				top++;
			}
			st[keri]++;
		}
	}

	long int odg = 0;
	for(int i = 0; i < 800000000; i++){
		//if(st[i] > 1){
			odg += (long)st[i]*(st[i]-1);
		//}
	}

	//Dodamo vse velikane
	int velikan;
	long visina;
	for(int i = 0; i < top; i++){
		velikan = overflows[i];
		//Ignoriraj mrtve
		if(velikan>-1){
			visina = HUGE + st[velikan];
			for(int j = i + 1; j < top; j++){
				//Vse duplikate ubit
				if(velikan == overflows[j]){
					visina += HUGE;
					overflows[j] = -1; //To je umor
				}
			}
			//Daj bek napaÄ?ni del odgovora:
			odg -= (long)st[velikan]*(st[velikan]-1);
			//Dodaj pravilni del:
			odg += visina*(visina-1);
		}
	}

	odg /= 2;

	cout << odg;

	return 0;
}