Ускорение программы С++

[rUs_LAN]

Вот задача вот прямо здесь. Если коротко то нужно проверить принадлежность точки прямоугольнику.

У входного файла есть много строк типа

6 6 3 6 6 9 8 7 5 4

где 6 6 - координаты точки

36 69 87 85 4 точки прямоугольника.

Ну вот моя программа

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

inline float round(float r) {
    return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
}

inline float lenght(int a1, int a2, int b1, int b2)
{
	int t1 = b1 - a1;
	int t2 = b2 - a2;
	
	return (sqrt((float)(t1*t1+t2*t2)));
}

inline float rectangle_square(int a1, int a2, int b1, int b2, int c1, int c2)
{
	float a = lenght(a1,a2,b1,b2);
	float b = lenght(a1,a2,c1,c2);
	
	return a * b;
}

inline float triangle_square(int x1, int y1, int x2, int y2, int x3, int y3)
{

	return (1/2.0 * fabs((x1-x3)*(y2-y3)-(x2-x3)*(y1-y3)));
}

int main(int argc, char **argv)
{
	ifstream in("input.txt");
	ofstream ou("output.txt");
	
	int vacationers_count;
	in >> vacationers_count;
	
	int **data = new int *[vacationers_count];
	for(int i = 0; i < vacationers_count; i++)
	{
		data[i] = new int[10];
	}
	
	for(int i = 0; i < vacationers_count; i++)
	{
		in >> data[i][0];
		in >> data[i][1];
		in >> data[i][2];
		in >> data[i][3];
		in >> data[i][4];
		in >> data[i][5];
		in >> data[i][6];
		in >> data[i][7];
		in >> data[i][8];
		in >> data[i][9];
	}
	

	int result = 0;
	float sAB, sBC, sCD, sDA;
	for(int i = 0; i < vacationers_count; i++)
	{
		sAB = triangle_square(data[i][2], data[i][3], data[i][4], data[i][5], data[i][0], data[i][1]);
		sBC = triangle_square(data[i][4], data[i][5], data[i][6], data[i][7], data[i][0], data[i][1]);
		sCD = triangle_square(data[i][6], data[i][7], data[i][8], data[i][9], data[i][0], data[i][1]);
		sDA = triangle_square(data[i][8], data[i][9], data[i][2], data[i][3], data[i][0], data[i][1]);

		float rec = rectangle_square(data[i][2], data[i][3], data[i][4], data[i][5], data[i][8], data[i][9]);	
		
		cout << (sAB + sBC + sCD + sDA) << "  " << rec << endl;
		
		int sums = round(sAB + sBC + sCD + sDA);
		
		if(sums == round(rec)) result++;
	}

	
	cout << result << endl;
	ou << result;
	
	for(int i = 0; i < vacationers_count; i++) delete [] data[i];
	delete [] data;
	
	ou.close();
	in.close();

	
	return 0;
}

я забрал с нее все сложные типи данных такие как структуры и т д, зделал все функции инлайн, ну короче упростил как мог, но все равно на етом сайте не проходить условие по времени.

Суть программы такова.

сначала запольняеться динамический массив данных.

потом идет работа по строкам сама идея в том чтоб поделить прямоугольник на 4 триугольника и пощитать их площадь и если она совпадет с площадю прямоугольника тогда точка принадлежыт прямоугольнику. Теперь больше конкретики

inline float round(float r) - округление

inline float lenght длина отрезка по 2 точкам

inline float rectangle_square площадь прямоуголькика по 3 точкам

inline float triangle_square площадь треугольника какаято хитрая формула

ну вот и все если знаете как ето ускорить напишите пожалуйста или посоветуйте какойто профайлер, я понимаю что ето не та задача где ето действительно нужно но посмотреть можно.

p.s. писал без транслейтера и спеллчекера поетому не сильно удивляйтесь моей неграмотности в русском языке.

[Ezhuk]

Можно попробовать "вращать стеку координат":
1) найти угол между Ох и любой стороной (используя арктангенс)
2) повернуть точки на найденный угол, для прямоугольника достаточно всего две противоположных
(а т.к. координаты даны последовательно, то это не трудно).
3) сравнить координаты точки с этими двумя точками.

Должно быть быстрее, да и проще =)

И я не очень понял функцию round.
Вроде самая простая реализация это

 floor(var+ 0.5)

Вот иллюстрация кода:

#include <iostream>
#include <cmath>
#include <algorithm>
struct Point{
	double x;
	double y;
};

double find_angle( Point A, Point B){
	return atan((B.y-A.y)/(B.x - A.x));
}
Point turn( Point R, double angle){
	double tx=R.x;
	R.x = R.x*cos(angle) - R.y*sin(angle);
	R.y = R.y*cos(angle) + tx*sin(angle);
	return R;
}

int main(){
	Point arr[5];
	arr[0].x = 6; arr[0].y= 6;
	arr[1].x = 3; arr[1].y= 6;
	arr[2].x = 6; arr[2].y= 9;
	arr[3].x = 8; arr[3].y= 7;
	arr[4].x = 5; arr[4].y= 4;
	
	double angle = find_angle(arr[1],arr[2]);
	Point T = turn(arr[0],angle);
//поворачиваем противоположные точки прямоугольника
// Можно 2 и 4, по настроению =)
	Point T1 = turn(arr[1],angle); 
	Point T3 = turn(arr[3],angle);

	double TX = std::max(T1.x,T3.x); // верхняя грань 
	double BX = std::min(T1.x,T3.x); // нижняя грань
	double LY = std::min(T1.y,T3.y); // грань слева
	double RY = std::max(T1.y,T3.y); // грань справа

	if( T.x < BX || T.x > TX || T.y > RY || T.y < LY )
		std::cout<<"OUT\n";
	else
		std::cout<<"IN\n";
	return 0;
}

[netrino]

Структуры можно вернуть, на производительности это не скажется, зато читабельней будет. А вот необходимость заводить массив в дин. памяти сомнительна. Достаточно иметь переменные для всех пяти координат, ведь после того, как выясняется попал дачник на свою площадку или нет, информация об этом конкретном дачнике и его площадке боле не нужна и её можно затереть данными о следующем дачнике. Уберите одну размерность у массива и ввод данных производите в том же цикле, где и обработку

[rUs_LAN]

Переписывать заново программу уже не было сил, и не было необходимости. Я сделал советы которые сказал netrino и этого хватило чтобы сдать эту программу.

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

inline double round(double r) {
    return floor(r + 0.5);
}

inline double lenght(int a1, int a2, int b1, int b2)
{
	int t1 = b1 - a1;
	int t2 = b2 - a2;
	
	return (sqrt((double)(t1*t1+t2*t2)));
}

inline double rectangle_square(int a1, int a2, int b1, int b2, int c1, int c2)
{
	double a = lenght(a1,a2,b1,b2);
	double b = lenght(a1,a2,c1,c2);
	
	return a * b;
}

inline double triangle_square(int x1, int y1, int x2, int y2, int x3, int y3)
{

	return (1/2.0 * abs((x1-x3)*(y2-y3)-(x2-x3)*(y1-y3)));
}

int main(int argc, char **argv)
{
	ifstream in("input.txt");
	ofstream ou("output.txt");
	
	int vacationers_count;
	in >> vacationers_count;
	
	int data0, data1, data2, data3, data4, 
		data5, data6, data7, data8, data9;
	
	int result = 0;
	double sAB, sBC, sCD, sDA, rec;
	for(int i = 0; i < vacationers_count; i++)
	{
		in >> data0;
		in >> data1;
		in >> data2;
		in >> data3;
		in >> data4;
		in >> data5;
		in >> data6;
		in >> data7;
		in >> data8;
		in >> data9;
		
		sAB = triangle_square(data2, data3, data4, data5, data0, data1);
		sBC = triangle_square(data4, data5, data6, data7, data0, data1);
		sCD = triangle_square(data6, data7, data8, data9, data0, data1);
		sDA = triangle_square(data8, data9, data2, data3, data0, data1);
		
		rec = rectangle_square(data2, data3, data4, data5, data8, data9);	
		
		int sums = round(sAB + sBC + sCD + sDA);		
		if(sums == round(rec)) result++;
		
	}
	
	cout << result << endl;
	ou << result;
	
	
	ou.close();
	in.close();

	
	return 0;
}

[Somebody]

#include <istream>
#include <fstream>

struct Point
{
	double x, y;
};

std::istream& operator>>(std::istream& stream, Point& point)
{
	return stream >> point.x >> point.y;
}

double CrossProduct(const Point& p0, const Point& p1, const Point& p2)
{
	return (p1.x - p0.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p1.y - p0.y);
}

bool IsInside(const Point& p0, const Point (&pp)[4])
{
	double
		prod0 = CrossProduct(p0, pp[0], pp[1]),
		prod1 = CrossProduct(p0, pp[1], pp[2]),
		prod2 = CrossProduct(p0, pp[2], pp[3]),
		prod3 = CrossProduct(p0, pp[3], pp[0]);
	return
		prod0 >= 0 && prod1 >= 0 && prod2 >= 0 && prod3 >= 0 ||
		prod0 <= 0 && prod1 <= 0 && prod2 <= 0 && prod3 <= 0;
}

int main()
{
	using namespace std;
	ifstream in("input.txt");
	ofstream out("output.txt");
	int count;
	in >> count;
	int result = 0;
	for (int i = 0; i < count; i++)
	{
		Point p0, pp[4];
		in >> p0 >> pp[0] >> pp[1] >> pp[2] >> pp[3];
		result += IsInside(p0, pp);
	}
	out << result;
}