Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 我会说我一遍AC了吗=。=

Posted by ecjtu_yuweiwei at 2014-07-27 15:12:07 on Problem 3384
```/*

*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
const int INF=0x7fffffff;
const double eps=1e-8;
const double PI=acos(-1.0);
const double inf=1e5;
const int Max=2001;
#define zero(x) (((x)>0?(x):-(x))<eps)
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int sign(double x)
{
return (x>eps)-(x<-eps);
}
typedef struct Node
{
double x;
double y;
Node(const double &_x=0, const double &_y=0) : x(_x), y(_y) {}
void input()
{
cin>>x>>y;
}
void output()
{
cout<<x<<" "<<y<<endl;
}
}point;
point list[Max],stack[Max];
point qq[Max],pp[Max],pnt[Max];
int n;
int top;

int cnt;
int curcnt;
double xmult(point p0,point p1,point p2)
{
return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double Distance(point p1,point p2)// 返回两点之间欧氏距离
{
return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );
}
bool cmp(point p1,point p2)
{
double temp;
temp=xmult(list[0],p1,p2);
if(temp>0)
return true;
if(temp==0&&(Distance(list[0],p1)<Distance(list[0],p2)))
return true;
return false;
}
void Init(int n)
{
int i;
for(i=1;i<=n;i++)
{
pp[i]=pnt[i];
}
pp[n+1]=pnt[1];
pp[0]=pnt[n];
cnt=n;
}
void GetLine(point u,point v,double &a,double &b,double &c)
{
a=v.y-u.y;
b=u.x-v.x;
c=v.x*u.y-u.x*v.y;
}
point Intersect(point u,point v,double a,double b,double c)
{
double q=fabs(a*u.x+b*u.y+c);
double p=fabs(a*v.x+b*v.y+c);
point res;
res.x=((p*u.x+q*v.x)/(q+p));
res.y=((p*u.y+q*v.y)/(q+p));
return res;
}
void CutLine(double a,double b,double c)
{
int i;
curcnt=0;
for(i=1;i<=cnt;i++)
{
if(sign(a*pp[i].x+b*pp[i].y+c)>=0)
{
qq[++curcnt]=pp[i];
}
else
{
if(sign(a*pp[i-1].x+b*pp[i-1].y+c)>0)
{
qq[++curcnt]=Intersect(pp[i],pp[i-1],a,b,c);
}
if(sign(a*pp[i+1].x+b*pp[i+1].y+c)>0)
{
qq[++curcnt]=Intersect(pp[i],pp[i+1],a,b,c);
}
}
}
for(i=1;i<=curcnt;i++)
{
pp[i]=qq[i];
}
pp[curcnt+1]=pp[1];
pp[0]=pp[curcnt];
cnt=curcnt;
}
bool solve(double r)//多边形每条边向内推进r距离得到新的多边形
{
Init(n);
int i;
double kk,a,b,c;
point ta,tb,tt;
for(i=1;i<=n;i++)
{
tt.x=pnt[i+1].y-pnt[i].y;
tt.y=pnt[i].x-pnt[i+1].x;
kk=r/sqrt(tt.x*tt.x+tt.y*tt.y);
tt.x=tt.x*kk;
tt.y=tt.y*kk;
ta.x=pnt[i].x+tt.x;
ta.y=pnt[i].y+tt.y;
tb.x=pnt[i+1].x+tt.x;
tb.y=pnt[i+1].y+tt.y;
GetLine(ta,tb,a,b,c);
CutLine(a,b,c);
}
if(cnt<=0)
return false;
return true;
}
int main()
{
int m,i,j;
int ra,rb;
double r;
double maxn,temp;
while(cin>>n>>r)
{
for(i=1;i<=n;i++)
pnt[i].input();
pnt[n+1]=pnt[1];
//Init(n);
solve(r);
ra=0;
rb=0;
maxn=-99999;
for(i=1;i<=cnt;i++)
{
for(j=i+1;j<=cnt;j++)
{
temp=Distance(pp[i],pp[j]);
if(temp>maxn)
{
maxn=temp;
ra=i;
rb=j;
}
}
}
cout<<setprecision(4)<<setiosflags(ios::fixed)<<pp[ra].x<<" "<<pp[ra].y<<" "<<pp[rb].x<<" "<<pp[rb].y<<endl;
}
return 0;
}
/*
5 2
-2 0
-5 3
0 8
7 3
5 0

4 3
0 0
0 8
10 8
10 0

*/
```

Followed by:

User ID:
Title:

Content: