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

wa无数次后终于过了,贴代码

Posted by idead at 2015-09-06 10:07:16 on Problem 1031
#include "math.h"
#include<iostream>
# define M_PI       3.14159265358979323846
#define DBL_MAX         1.7976931348623158e+308
using namespace std;
double polyX[100], polyY[100], theta[100];
int polySides;
bool pointInPolygon();
double max(double theta1, double theta2);
double min(double theta1, double theta2);
double angle(int i);
void correct(int i, int j);
int main()
{
	double k, h,I=0,thetamax=0,thetamin=DBL_MAX,whole;
	int i,j;
	cin >> k >> h >> polySides;
	whole = k*h * 2 * M_PI;
	whole *= 100;
	whole = (int)(whole + 0.5);
	whole /= 100.0;
	for (i = 0; i < polySides; i++)
	{
		cin >> polyX[i] >> polyY[i];
	}
	if (pointInPolygon())
	{
		printf("%.2lf", whole);
		return 0;
	}
	for (i = 0; i < polySides; i++)
	{
		theta[i] = angle(i);
	}
	j = polySides - 1;
	for (i = 0; i < polySides; i++)
	{
		correct(i, j);
		j = i;
	}
	j = polySides - 1;
	for (i = 0; i < polySides; i++)
	{
		double maxt, mint;
		maxt = max(theta[i], theta[j]);
		mint = min(theta[i], theta[j]);
		thetamax = max(thetamax, maxt);
		thetamin = min(thetamin, mint);
		j = i;
	}
	I =(thetamax-thetamin)*k*h;
	if (I > whole) I = whole;
	I *= 100;
	I =(int)(I+0.5);
	I /= 100.0;
	printf("%.2lf", I);
}
bool pointInPolygon() {

	int   i, j = polySides - 1;
	bool  oddNodes = false;

	for (i = 0; i<polySides; i++) {
		if (polyY[i]<0 && polyY[j] >= 0
			|| polyY[j]<0&& polyY[i] >= 0) {
			if (polyX[i] + (0 - polyY[i]) / (polyY[j] - polyY[i])*(polyX[j] - polyX[i])<0) {
				oddNodes = !oddNodes;
			}
		}
		j = i;
	}

	return oddNodes;
}
double max(double theta1, double theta2)
{
	return theta1 > theta2 ? theta1 : theta2;
}
double min(double theta1, double theta2)
{
	return theta1 > theta2 ? theta2 : theta1;
}
double angle(int i)
{
	double anglet;
	if (polyX[i] == 0)
	{
		anglet = polyY[i]>0 ? M_PI / 2.0 : M_PI * 3 / 2.0;
	}
	else{
		anglet = atan(polyY[i] / polyX[i]);
		if (polyX[i] < 0)
			anglet += M_PI;
		else if (polyX[i] > 0 && polyY[i] < 0)
			anglet += 2 * M_PI;
	}
	return anglet;
}
void correct(int i, int j)
{
	if (theta[i]>theta[j] && theta[i] - theta[j] > M_PI)
	{
		theta[j] += 2 * M_PI;
		correct(j, j - 1>=0?j-1:polySides-1);
	}
	else if (theta[j] > theta[i] && theta[j] - theta[i] > M_PI)
	{
		theta[i] += 2 * M_PI;
		correct(i + 1 < polySides ? i + 1 : 0, i);
	}
}

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