| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
水水过~~~附代妈,47秒#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator