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

水水过~~~附代妈,47秒

Posted by KatrineYang at 2016-07-12 08:25:41 on Problem 1113
#include <iostream>
#include <cmath>
using namespace std;

const double PI = 3.141592654;

class node{
public:
	int x;
	int y;
	node *next;
	node *prev;
	node(int X, int Y): x(X), y(Y){
		next = this;
		prev = this;
	}
};

bool you(node *n1, node *n2, node *n3){
	int x1 = n2->x - n1->x, y1 = n2->y - n1->y, x2 = n3->x - n2->x, y2 = n3->y - n2->y;
	return x1*y2>y1*x2;
}

double dist(node *n1, node *n2){
	return sqrt(0.0 + (n2->x - n1->x) * (n2->x - n1->x) + (n2->y - n1->y) * (n2->y - n1->y));
}

int main() {
	int n, l;
	cin >> n >> l;
	node *head, *tail;
	int x1, y1;
	cin >> x1 >> y1;
	node *temp = new node(x1, y1);
	head = temp;
	tail = temp;
	for(int i = 0; i < n-1; i++){
		cin >> x1 >> y1;
		node *tmp = new node(x1, y1);
		head->prev = tmp;
		tail->next = tmp;
		tmp->prev = tail;
		tmp->next = head;
		tail = tmp;
	}
	int cnt = 0;
	while(1){
		if(you(head->prev, head, head->next)){
			n--;
			cnt=0;
			head->prev->next = head->next;
			head->next->prev = head->prev;
			head = head->next;
		}
		else{
			head = head->next;
			cnt++;
			if(cnt >= n) break;
		}
	}
	double sum = 2 * PI * l;
	for(int i = 0; i < n; i++){
		sum += dist(head, head->next);
		head = head->next;
	}
	int isum = (int) sum;
	if(sum-isum < 0.5) cout << isum << endl;
	else cout << isum+1 << endl;
	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