Code: Select all
removed
Moderator: Board moderators
Code: Select all
removed
Code: Select all
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define SQ(x) (x)*(x)
#define INF INT_MAX / 2
#define x first
#define y second
long long N, M, L;
vector < pair < long long, long long > > t;
double dist( pair < long long, long long > &a, pair < long long, long long > &b ) {
long long dx = a.x - b.x;
long long dy = a.y - b.y;
return sqrt( (double)(dx*dx + dy*dy) );
}
bool ccw( const pair < long long, long long > &a, const pair < long long, long long > &b, const pair < long long, long long > &c ) {
long long x = a.x*(b.y-c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
return ( x > 0 );
}
bool cmp( const pair < long long, long long > &a, const pair < long long, long long > &b ) {
return ccw( t[0], a, b );
}
long double convex() {
long long min_x = INF, min_y = INF, koja = -1;
for( int i = 0; i < t.size(); ++i )
if( min_x > t[i].x || ( min_x == t[i].x && min_y > t[i].y ) ) {
min_x = t[i].x; min_y = t[i].y;
koja = i;
}
swap( t[0], t[koja] );
sort( t.begin(), t.end(), cmp );
t.pb( t[0] );
vector < pair < long long, long long > > CH;
CH.pb( t[0] );
CH.pb( t[1] );
for( int i = 2; i < t.size(); ++i ) {
while( !ccw( CH[CH.size()-2], CH[CH.size()-1], t[i] ) )
CH.pop_back();
CH.pb( t[i] );
}
long double ret = 0.0;
for( int i = 0; i < CH.size()-1; ++i )
ret += dist( CH[i], CH[i+1] );
return ret;
}
int main() {
scanf( "%d", &M );
for( int i = 0; i < M; ++i ) {
scanf( "%d %d", &L, &N ); t.resize( N );
for( int j = 0; j < N; ++j ) scanf( "%d %d", &t[j].x, &t[j].y );
long double rjesenje = convex();
printf( "%.5llf\n", max( convex(), (long double)L ) );
}
return 0;
}
Code: Select all
#include<cmath>
#include<stdio.h>
#include<iostream>
using namespace std;
long double P;
struct point {
long long x,y;
point& operator =(point &other) { x=other.x; y=other.y; return (*this); }
bool operator ==(point &other) {
if(x==other.x&&y==other.y) return true;
return false;
}
bool operator != (point &other) {
if((*this)==other) return false;
return true;
}
double operator-(point &other) {
return (sqrt((long double)(x-other.x)*(x-other.x)+(y-other.y)*(y-other.y)));
}
};
void main() {
point points[100];
bool node[100];
P=acos(-1.0);
long long i,j,t,num,step,min,best;
long double Isize,Fsize,angel,mangel,cangel,dx,dy;
point start,cur;
cin>>t;
while(t) {
min=10000;
cin>>Isize>>num;
Fsize=0;
for(i=0;i<num;i++) {
cin>>points[i].x>>points[i].y;
node[i]=true;
for(j=0;j<i;j++) {
if(points[j]==points[i]) {
num--;
i--;
break;
}
}
if(points[i].y<min||(!i)) {
min=points[i].y;
start=points[i];
best=i;
}
}
bool sw=true;
cur=start;
if(num==1) Fsize=0;
else {
step=0;
cangel=0;
while(sw) {
mangel=9;
for(i=0;i<num;i++) {
if(node[i]&&points[i]!=cur) {
dx=points[i].x-cur.x;
dy=points[i].y-cur.y;
angel=atan2(dy,dx);
if(angel<0) angel+=(2*P);
if(angel<=mangel) {
if(angel==mangel&&(abs(dx)>abs((long double)(points[best].x-cur.x)))) {
node[best]=false;
best=i;
}
else if(angel==mangel) node[i]=false;
else {
best=i;
mangel=angel;
}
}
}
}
node[best]=false;
step++;
Fsize+=(points[best]-cur);
cangel=mangel;
cur=points[best];
if(cur==start) sw=false;
}
}
if(step==2) Fsize/=2;
if(Fsize<Isize) printf("%.5lf\n",(long double)Isize);
else printf("%.5lf\n",Fsize);
t--;
}
}
My AC code givesLarry wrote:In the N = 2 case, say
1 2
0 1
0 2
are we suppose to print "2" or "1"? Thanks!
Code: Select all
2.00000
Code: Select all
Dear H_Hima:
You are trying to solve "Nails" (problem 11096).
I have received and stored your C++ program. It will be compiled and
run
as soon as possible; please be patient waiting for the results...
--
The Online Judge
--------------- The program I'll compile begins here: ---------------
#include <cmath>
#include <cstdio>
#include <stdlib.h>
#include<iostream>
using namespace std;
const long double P=acos(-1.0);
struct point{
long long x,y;
long double ang;
}a[110],b[110];
long double atan2(point a,point b) {
if(a.x==b.x&&a.y==b.y) return 0;
long double ang=atan2((long double)b.y-a.y,b.x-a.x);
if(ang<0) ang+=2*P;
return ang;
}
int comp(const void *a,const void *b) {
point A=*(point *)a,B=*(point *)b;
if(A.ang>B.ang) return 1;
if(A.ang<B.ang) return -1;
return 0;
}
long long convexhull(long long n) {
long long i,count,m=-1;
long double d1,d2;
point temp;
for(i=0;i<n;i++) {
if(m==-1||a[m].y>a[i].y||(a[m].y==a[i].y&&a[m].x<a[i].x))
m=i;
}
temp=a[m];
a[m]=a[0];
a[0]=temp;
a[0].ang=0;
a[n]=a[0];
for(i=1;i<n;i++)
a[i].ang=atan2(a[0],a[i]);
qsort(a,n,sizeof(point),comp);
count=1;
b[0]=a[0];
b[1]=a[1];
if(n<3) {
b[n]=a[0];
return n+1;
}
for(i=2;i<=n;i++) {
count++;
b[count]=a[i];
d1=atan2(b[count-2],b[count-1]);
d2=atan2(b[count-1],b[count]);
while(d2&&d2<d1) {
b[count-1]=b[count];
count--;
d1=atan2(b[count-2],b[count-1]);
d2=atan2(b[count-1],b[count]);
}
}
return count+1;
}
void main() {
long long i,t,init,n,count;
long double len;
cin>>t;
while(t) {
cin>>init>>n;
for(i=0;i<n;i++) cin>>a[i].x>>a[i].y;
count=convexhull(n);
len=0;
for(i=1;i<count;i++)
len+=sqrt((long
double)(b[i-1].x-b[i].x)*(b[i-1].x-b[i].x)+(b[i-1].y-b[i].y)*(b[i-1].y-b[i].y));
if(len<init) len=init;
printf("%.5lf\n",len);
t--;
}
}
Code: Select all
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
typedef struct
{
long long x;
long long y;
}Point;
Point point[101];
Point p0;
long stack[101];
long long ps;
long long i,a;
long long l,n;
long long x,y;
long double P;
int compare(const void *a, const void *b);
void Convex_Hull(long n);
int main(){
scanf("%lld",&a);
while(a>0){
a--;
scanf("%lld %lld",&l,&n);
for(i=0;i<n;i++)
scanf("%lld %lld",&point[i].x,&point[i].y);
if(n>2){
qsort(point,n,sizeof(point[0]),compare);
Convex_Hull(n);
P=0;
x=point[stack[1]].x;
y=point[stack[1]].y;
for(i=2;i<ps;i++){
P+=sqrt( (point[stack[i]].x-x)*(point[stack[i]].x-x) + (point[stack[i]].y-y)*(point[stack[i]].y-y) );
x=point[stack[i]].x;
y=point[stack[i]].y;
}
i=1;
P+=sqrt( (point[stack[i]].x-x)*(point[stack[i]].x-x) + (point[stack[i]].y-y)*(point[stack[i]].y-y) );
}
else
{
if(n==2)
P=sqrt( (point[0].x-point[1].x)*(point[0].x-point[1].x) + (point[0].y-point[1].y)*(point[0].y-point[1].y) );
else
P=0;
}
if(P>l)
printf("%.5llf\n",P);
else
printf("%lld.00000\n",l);
}
return 0;
}
long long cross_product(Point a, Point b, Point c)
{
return (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y);
}
int compare(const void *a, const void *b)
{
long long k, d1, d2;
Point *sp1 = (Point *)a;
Point *sp2 = (Point *)b;
k = cross_product(p0,*sp1,*sp2);
if(k > 0)
return -1;
else if(k == 0)
{
d1 = (sp1->x - p0.x)*(sp1->x - p0.x) + (sp1->y - p0.y)*(sp1->y - p0.y);
d2 = (sp2->x - p0.x)*(sp2->x - p0.x) + (sp2->y - p0.y)*(sp2->y - p0.y);
if(d1 < d2)
return -1;
else
return 1;
}
else
return 1;
}
void Convex_Hull(long n)
{
long long i;
stack[1] = 0;
stack[2] = 1;
stack[3] = 2;
ps = 3;
for(i=2; i<n; ++i)
{
while(cross_product(point[stack[ps]], point[stack[ps-1]], point[i]) >= 0)
{
ps--;
if(ps == 1) break;
}
ps++;
stack[ps] = i;
}
if(cross_product(point[stack[ps]], point[stack[ps-1]], point[stack[1]]) >= 0)
ps--;
stack[ps+1] = stack[1];
ps++;
}
Code: Select all
2
1 2
1 0
2 0
1 3
1 0
2 0
3 0
Code: Select all
2.00000
4.00000