Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

老是超时。。。帮忙看看?

Posted by openware at 2010-01-12 21:32:18 on Problem 2954
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;

int main()
{
	int x1, y1, x2, y2, x3, y3;
	int cnt = 0;
	int dot = 0;

	int BA[3];
	int BC[3];
	int BCXBA[3];

	int xMinMax[2];
	int yMinMax[2];

	int i, j;

	while (1) {
		scanf("%d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3);
		if (x1||y1||x2||y2||x3||y3) {
			BA[0] = x1-x2;
			BC[0] = x3-x2;
			BA[1] = y1-y2;
			BC[1] = y3-y2;
			BA[2] = BC[2] = 0;

			BCXBA[0] = BC[1]*BA[2] - BC[2]*BA[1];
			BCXBA[1] = BC[2]*BA[0] - BC[0]*BA[2];
			BCXBA[2] = BC[0]*BA[1] - BC[1]*BA[0];

			xMinMax[0] = min(min(abs(x3 - x2), abs(x3 - x1)), abs(x2 - x1));
			xMinMax[1] = max(max(abs(x3 - x2), abs(x3 - x1)), abs(x2 - x1));

			yMinMax[0] = min(min(abs(y3 - y2), abs(y3 - y1)), abs(y2 - y1));
			yMinMax[1] = max(max(abs(y3 - y2), abs(y3 - y1)), abs(y2 - y1));

			for (i = xMinMax[0]+1; i < xMinMax[1]; i++)
				for (j = yMinMax[0]+1; j < yMinMax[1]; j++) {
					int BP[3] = {i-x2, j-y2, 0};
					int BCXBP[3] = {BC[1]*BP[2] - BC[2]*BP[1],
						BC[2]*BP[0] - BC[0]*BP[2], BC[0]*BP[1] - BC[1]*BP[0]};
					dot = BCXBA[0]*BCXBP[0]+BCXBA[1]*BCXBP[1]+BCXBA[2]*BCXBP[2];
					if (dot > 0)
						cnt++;
				} //for
			printf("%d\n", cnt);
		} //if
		else break;
	} //while
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator