rendered paste body#include "stdafx.h"#include "Animal.h"#include <algorithm>#define PI 3.14159265fstd::vector<Animal*> dogs;std::vector<Animal*> cats;std::vector<Animal*> mice;std::vector<Animal*> dogHull;std::vector<Animal*> catHull;Animal* dogPivot;Animal* catPivot;struct AnimalCircle{ double X, Y, RadiusSq;};AnimalCircle* dogMax;AnimalCircle* catMax;AnimalCircle* dogInsideHull;AnimalCircle* catInsideHull;void FillCoordinate(const char* str, Animal* animal){ int stringLength = -1; while(str[++stringLength] != 0) { } int pow = 1; int space = 0; for(int l = stringLength - 1; l >= 0; l--) { if(str[l] == ' ') { pow = 1; animal->Y = animal->X; animal->X = 0; space = l; } else if(str[l] >= 48) { animal->X += (str[l] - 48) * pow; pow *= 10; } } if(str[0] == '-') animal->X *= -1; if(str[space + 1] == '-') animal->Y *= -1;}Animal* testPivot;int testCallCount = 0;inline bool Test(const Animal* a, const Animal* b){ testCallCount++; if(a->Angle < b->Angle) return true; else if(a->Angle > b->Angle) return false; else { double aDistSq = ((testPivot->X - a->X) * (testPivot->X - a->X)) + ((testPivot->Y - a->Y) * (testPivot->Y - a->Y)); double bDistSq = ((testPivot->X - b->X) * (testPivot->X - b->X)) + ((testPivot->Y - b->Y) * (testPivot->Y - b->Y)); if(aDistSq < bDistSq) return true; else if(aDistSq > bDistSq) return false; else return false; }}double sortTime;void SortAnimalsByCartesianAngle(std::vector<Animal*>& animals, Animal& pivot){ sortTime = 0; LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); LARGE_INTEGER start; QueryPerformanceCounter(&start); for(std::vector<Animal*>::iterator iter = animals.begin(); iter != animals.end(); iter++) { Animal* animal = *iter; double dX = animal->X - pivot.X; double dY = animal->Y - pivot.Y; if (dX > 0 && dY > 0) animal->Angle = atan(dY / dX);// * _180BYPI; else if (dX < 0 && dY > 0) animal->Angle = atan(-dX / dY) + (PI / 2);// * _180BYPI + 90.f; else if (dX < 0 && dY < 0) animal->Angle = atan(dY / dX) + PI;// * _180BYPI + 180.f; else if (dX > 0 && dY < 0) animal->Angle = atan(-dX / dY) + (PI * 1.5f);// * _180BYPI + 270.f; else if (dX == 0 && dY > 0) animal->Angle = (PI / 2); else if (dX < 0 && dY == 0) animal->Angle = PI; else if (dX == 0 && dY < 0) animal->Angle = PI * 1.5f; else animal->Angle = 0; } testPivot = &pivot; //bool(*fn_pt)(const Animal*, const Animal*) = Test; //multiset<Animal*, bool(*)(const Animal*, const Animal*)> ms(fn_pt); //for(int i = 0; i< animals.size(); i++) // ms.insert(animals[i]); sort(animals.begin(), animals.end(), Test); LARGE_INTEGER end; QueryPerformanceCounter(&end); double diff = (double)end.QuadPart - (double)start.QuadPart; double timeD = diff / (double)freq.QuadPart; sortTime = timeD; //cout << "Sort time: " << (timeD * 1000) << "ms." << endl;}void GenerateConvexHull(std::vector<Animal*>& animals, std::vector<Animal*>& hull, Animal& pivot){ SortAnimalsByCartesianAngle(animals, pivot); hull.push_back(animals[0]); hull.push_back(animals[1]); unsigned int i = 2; int first = 1; int second = 0; while(i < animals.size()) { if(hull.size() > 1) { Animal* a = hull[second]; Animal* b = hull[first]; Animal* c = animals[i]; double orin = (b->X - a->X) * (c->Y - a->Y) - (c->X - a->X) * (b->Y - a->Y); if(orin > 0) { hull.push_back(animals[i++]); first++; second++; } else { hull.erase(hull.begin() + first); first--; second--; } } else { hull.push_back(animals[i++]); first++; second++; } } hull.push_back(animals[0]);}bool IsContainedInConvex(vector<Animal*>& animals, Animal* mouse){ for(unsigned int i = 0; i < animals.size() - 1; i++) { Animal* a = animals[i]; Animal* b = animals[i + 1]; double orin = (b->X - a->X) * (mouse->Y - a->Y) - (mouse->X - a->X) * (b->Y - a->Y); if(orin < 0) return false; } return true;}AnimalCircle* GenerateMaxBoundingCircle(vector<Animal*>& animals){ double totalX = 0; double totalY = 0; double maxRadiusSq = 0; int numAnimals = animals.size(); for(unsigned int i = 0; i < numAnimals; i++) { Animal* animal = animals[i]; totalX += animal->X; totalY += animal->Y; } totalX /= numAnimals; totalY /= numAnimals; for(unsigned int i = 0; i < numAnimals; i++) { Animal* animal = animals[i]; double distSq = ((totalX - animal->X) * (totalX - animal->X)) + ((totalY - animal->Y) * (totalY - animal->Y)); if(distSq > maxRadiusSq) maxRadiusSq = distSq; } AnimalCircle* circle = new AnimalCircle(); circle->X = totalX; circle->Y = totalY; circle->RadiusSq = maxRadiusSq; return circle;}AnimalCircle* GenerateInsideHullCircle(vector<Animal*>& animals, double midX, double midY){ AnimalCircle* insideCircle = new AnimalCircle(); insideCircle->X = midX; insideCircle->Y = midY; int numAnimals = animals.size(); double nearestDistSq = DBL_MAX; for(int i = 0; i < numAnimals - 1; i++) { Animal* a = animals[i]; Animal* b = animals[i+1]; double lengthSq = (b->X - a->X) * (b->X - a->X) + (b->Y - a->Y) * (b->Y - a->Y); double u = ((midX - a->X) * (b->X - a->X) + (midY - a->Y) * (b->Y - a->Y)) / lengthSq; double ipX = a->X + u * (b->X - a->X); double ipY = a->Y + u * (b->Y - a->Y); double distSq = (ipX - midX) * (ipX - midX) + (ipY - midY) * (ipY - midY); if(distSq < nearestDistSq) nearestDistSq = distSq; } insideCircle->RadiusSq = nearestDistSq; return insideCircle;}bool IsInsideCircle(AnimalCircle* circle, Animal* animal){ double distSq = ((circle->X - animal->X) * (circle->X - animal->X)) + ((circle->Y - animal->Y) * (circle->Y - animal->Y)); if(distSq < circle->RadiusSq) return true; else return false;}int numEaten = 0;int numNeither = 0;int numSafe = 0;double earlyOutDogs = 0;double earlyOutCats = 0;int numCHDogs = 0;int numCHCats = 0;void SolveProblem(int dataSetNum){ numEaten = 0; numNeither = 0; numSafe = 0; earlyOutDogs = 0; earlyOutCats = 0; numCHDogs = 0; numCHCats = 0; for(unsigned int m = 0; m < mice.size(); m++) { if(IsInsideCircle(dogInsideHull, mice[m])) { numSafe++; continue; } else { if(IsInsideCircle(dogMax, mice[m])) { numCHDogs++; if(IsContainedInConvex(dogHull, mice[m])) { numSafe++; continue; } } } //If here, not saved by dogs if(IsInsideCircle(catInsideHull, mice[m])) { numEaten++; continue; } else { if(IsInsideCircle(catMax, mice[m])) { numCHCats++; if(IsContainedInConvex(catHull, mice[m])) { numEaten++; continue; } } } //If here, neither numNeither++; } }void DeleteStuff(){ for(int d = 0; d < dogs.size(); d++) { delete dogs[d]; } for(int c = 0; c < cats.size(); c++) { delete cats[c]; } for(int m = 0; m < mice.size(); m++) { delete mice[m]; } delete dogPivot; delete catPivot; delete dogMax; delete catMax; delete dogInsideHull; delete catInsideHull;}int main(int argc, char* argv[]){ if(argc > 1) { double lowestTime = DBL_MAX; LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); while(true) { LARGE_INTEGER start; QueryPerformanceCounter(&start); std::ifstream dataFile(argv[1]); if(dataFile.is_open()) { //cout << "Load Started.\n"; dataFile.seekg(0, std::ios_base::end); const size_t file_size = dataFile.tellg(); dataFile.seekg(0, std::ios_base::beg); //cout << "Found file size.\n"; std::vector<char> buf(file_size); buf.resize(file_size); //cout << "Resized buffer.\n"; dataFile.read(&buf[0], file_size); //cout << "Read into char buffer.\n"; typedef std::vector<char*> vcs; vcs lines; std::vector<char>::iterator it = buf.begin(); //cout << "Load progressed...\n"; while (it != buf.end()) { lines.push_back(&*it); it = std::find(it, buf.end(), '\n'); if (it != buf.end()) *it++ = 0; } LARGE_INTEGER loadEnd; QueryPerformanceCounter(&loadEnd); //cout << "Load Complete.\n"; double loadDiff = (double)loadEnd.QuadPart - (double)start.QuadPart; double loadTime = loadDiff / (double)freq.QuadPart; int lineNum = 0; int numLines = lines.size(); int dataSetNum = 0; while(lineNum < numLines) { dogHull.clear(); catHull.clear(); dogs.clear(); cats.clear(); mice.clear(); string setHeader(lines[lineNum++]); int firstSpace = setHeader.find_first_of(" "); int secondSpace = setHeader.find_first_of(" ", firstSpace + 1); int numDogs = atoi(&setHeader[0]); int numCats = atoi(&setHeader[firstSpace + 1]); int numMice = atoi(&setHeader[secondSpace + 1]); if(numDogs + numCats + numMice == 0) break; Animal* dogPivot = new Animal(); Animal* catPivot = new Animal(); dogPivot->Y = FLT_MAX; catPivot->Y = FLT_MAX; for(int d = 0; d < numDogs; d++) { Animal* dog = new Animal(); FillCoordinate(lines[lineNum++], dog); if(dog->Y < dogPivot->Y) dogPivot = dog; dogs.push_back(dog); } for(int c = 0; c < numCats; c++) { Animal* cat = new Animal(); FillCoordinate(lines[lineNum++], cat); if(cat->Y < catPivot->Y) catPivot = cat; cats.push_back(cat); } for(int m = 0; m < numMice; m++) { Animal* mouse = new Animal(); FillCoordinate(lines[lineNum++], mouse); mice.push_back(mouse); } LARGE_INTEGER time; QueryPerformanceCounter(&time); double loadTimeDiff = (double)time.QuadPart - (double)start.QuadPart; double loadTimeD = loadTimeDiff / (double)freq.QuadPart; testCallCount = 0; double dogSortTime, catSortTime; GenerateConvexHull(dogs, dogHull, *dogPivot); dogSortTime = sortTime; GenerateConvexHull(cats, catHull, *catPivot); catSortTime = sortTime; dogMax = GenerateMaxBoundingCircle(dogHull); catMax = GenerateMaxBoundingCircle(catHull); dogInsideHull = GenerateInsideHullCircle(dogHull, dogMax->X, dogMax->Y); catInsideHull = GenerateInsideHullCircle(catHull, catMax->X, catMax->Y); QueryPerformanceCounter(&time); double ppTimeDiff = (double)time.QuadPart - (double)start.QuadPart; double ppTimeD = ppTimeDiff / (double)freq.QuadPart; SolveProblem(dataSetNum++); LARGE_INTEGER veryEnd; QueryPerformanceCounter(&veryEnd); double diff2 = (double)veryEnd.QuadPart - (double)start.QuadPart; double time2 = diff2 / (double)freq.QuadPart; if(time2 < lowestTime) { lowestTime = time2; cout << "----- NEW FASTEST RUN -----" << endl; cout << "Load time: " << (loadTimeD * 1000) << "ms." << endl; cout << "PP time: " << ((ppTimeD - loadTimeD) * 1000) << "ms." << endl; cout << "Proc time: " << (time2 - loadTimeD - (ppTimeD - loadTimeD)) * 1000 << "ms.\n"; cout << "Total time: " << (time2 * 1000) << "ms." << endl; cout << "Eaten: " << numEaten << ", Neither: " << numNeither << ", Safe: " << numSafe << "\n"; //cout << "Dog C.H. Tests: " << numCHDogs << "\n"; //cout << "Cat C.H. Tests: " << numCHCats << "\n"; //cout << "Dog Sort Time: " << dogSortTime * 1000 << "ms\n"; //cout << "Cat Sort Time: " << catSortTime * 1000 << "ms\n"; //cout << "TestCallCount: " << testCallCount << "\n"; cout << "---------------------------" << endl; } //else //{ // cout << "---------------------------" << endl; // cout << "Load time: " << (loadTimeD * 1000) << "ms." << endl; // cout << "PP time: " << ((ppTimeD - loadTimeD) * 1000) << "ms." << endl; // cout << "Proc time: " << (time2 - loadTimeD - (ppTimeD - loadTimeD)) * 1000 << "ms.\n"; // cout << "Total time: " << (time2 * 1000) << "ms." << endl; // cout << "Eaten: " << numEaten << ", Neither: " << numNeither << ", Safe: " << numSafe << "\n"; // //cout << "Dog C.H. Tests: " << numCHDogs << "\n"; // //cout << "Cat C.H. Tests: " << numCHCats << "\n"; // cout << "Dog Sort Time: " << dogSortTime * 1000 << "ms\n"; // cout << "Cat Sort Time: " << catSortTime * 1000 << "ms\n"; // //cout << "TestCallCount: " << testCallCount << "\n"; // cout << "---------------------------" << endl; //} DeleteStuff(); } buf.clear(); lines.clear(); } //cout << "Done deleting.\n"; dataFile.close(); } } return 0;}