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

buy one get another for free

Posted by yygy at 2023-05-16 12:06:38 on Problem 2850
// MyFirstApp.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

typedef __int64 lld;

const int MAXN = 512;

//经度角a, 纬度角b
double GeodesicDistance(double r, double a1, double b1, double a2, double b2)
{
	return r * acos(cos(b1) * cos(b2) * cos(a1 - a2) + sin(b1) * sin(b2));
}

struct Point
{
	double x, y;

	Point operator -(const Point& other) const
	{
		Point result;
		result.x = x - other.x;
		result.y = y - other.y;
		return result;
	}

	Point operator +(const Point& other) const
	{
		Point result;
		result.x = x + other.x;
		result.y = y + other.y;
		return result;
	}

	Point operator *(double c) const
	{
		Point result = *this;
		result.x *= c;
		result.y *= c;
		return result;
	}
};

static void Rotate90(Point& dir)
{
	double x = -dir.y;
	double y = dir.x;
	dir.x = x;
	dir.y = y;
}

Point Calc(const Point& a, const Point& b)
{
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	double h = sqrt(2.0 * 2 - (dx * dx + dy * dy) / 4);

	Point dir = b - a;

	double len = sqrt(dir.x * dir.x + dir.y * dir.y);
	dir.x /= len;
	dir.y /= len;

	Rotate90(dir);

	dir.x *= h;
	dir.y *= h;

	Point mid = (a + b) * 0.5;

	return dir + mid;
}

int main()
{
	int n;

	Point points[16][16];
	while (cin >> n && n > 0)
	{
		std::vector<double> xs;
		for(int i=0;i<n;i++)
		{
			double x;
			cin >> x;
			xs.push_back(x);
		}

		std::sort(xs.begin(), xs.end());

		for (int i = 0; i < n; i++)
		{
			points[0][i].x = xs[i];
			points[0][i].y = 1;
		}

		for (int row = 1; row < n; row++)
		{
			for (int i = 0; i < n - row; i++)
			{
				points[row][i] = Calc(points[row - 1][i], points[row - 1][i + 1]);
			}
		}

		double x = fabs(points[n - 1][0].x) < 1e-6 ? 0 : points[n - 1][0].x;

		double y = fabs(points[n - 1][0].y) < 1e-6 ? 0 : points[n - 1][0].y;

		printf("%.4f %.4f\n", x, y);
	}

	return 0;
}

/*
4 1.0 4.4 7.8 11.2
1 1.0
6 1.0 3.0 5.0 7.0 9.0 11.0
10 1.0 3.0 5.0 7.0 9.0 11.0 13.0 15.0 17.0 20.4
5 1.0 4.4 7.8 14.6 11.2
0
Sample Output

6.1000 4.1607
1.0000 1.0000
6.0000 9.6603
10.7000 15.9100
7.8000 5.2143
*/

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