| ||||||||||
| 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 | |||||||||
总是wrong answer,求指导以下是代码:
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <iomanip>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <cstdio>
#include <vector>
#include <limits>
#include <climits>
#include <list>
#include <memory>
using namespace std;
ifstream fin;
#define N_MAX 1200
#define PI 3.141592654
struct node{
int x, y;
};
node ns[N_MAX];
node an[N_MAX];
int n, l;
double vec(node beg1, node end1, node beg2, node end2)
{
int v1_x = end1.x - beg1.x;
int v1_y = end1.y - beg1.y;
int v2_x = end2.x - beg2.x;
int v2_y = end2.y - beg2.y;
return((double)v1_x * v2_y - v1_y * v2_x);
}
class compare2{
node pp;
public:
compare2(const node &cp): pp(cp){}
bool operator()(node a, node b){
double cross = vec(pp, a, pp, b);
if(cross > 0)
return(true);
else if(cross == 0){
int v1_x = a.x - pp.x;
int v1_y = a.y - pp.y;
int v2_x = b.x - pp.x;
int v2_y = b.y - pp.y;
double dist_a = v1_x * v1_x + v1_y * v1_y;
double dist_b = v2_x * v2_x + v2_y * v2_y;
return(dist_a < dist_b);
}
return(false);
}
};
double distan(node a, node b)
{
double tmp = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
return(sqrt(tmp));
}
void add_length(const vector<node> &ss);
void solve();
int main()
{
//fin.open("main.in");
//cin.rdbuf(fin.rdbuf());
while(cin >> n >> l){
memset(ns, 0, sizeof(ns));
for(int i = 0; i < n; ++ i)
cin >> ns[i].x >> ns[i].y;
solve();
}
return 0;
}
void solve()
{
int min_x = (~(1 << 31));
int min_idx;
for(int i = 0; i < n; ++ i){
if(min_x > ns[i].x){
min_x = ns[i].x;
min_idx = i;
}
else if(min_x == ns[i].x && ns[i].y <= ns[min_idx].y){
min_idx = i;
}
}
swap(ns[n - 1], ns[min_idx]);
node p0;
p0.x = ns[n - 1].x; p0.y = ns[n - 1].y;
sort(ns, ns + n - 1, compare2(p0));
vector<node> stk;
stk.push_back(p0);
stk.push_back(p0);
stk.push_back(ns[0]);
stk.push_back(ns[1]);
int index = 2;
while(index < n){
while(stk.size() >= 2 && vec(stk[(int)stk.size() - 2], ns[index],
stk[(int)stk.size() - 2], stk[(int)stk.size() - 1]) >= 0)
stk.pop_back();
stk.push_back(ns[index]);
++ index;
}
add_length(stk);
}
void add_length(const vector<node> &ss)
{
double length = 0;
for(int i = 1; i < (int)ss.size(); ++ i){
if(i != (int)ss.size() - 1)
length += distan(ss[i + 1], ss[i]);
else
length += distan(ss[0], ss[i]);
}
length += 2 * PI * l;
printf("%.0f\n", length);
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator