来个有缘人
#include<bits/stdc++.h>
using namespace std;
#define int __int128
void _print(__int128 x,bool first=true){
if(x<0){
putchar('-');
_print(-x,false);
return;
}
if(x==0){
if(first) putchar('0');
return;
}
_print(x/10,false);
putchar((int)(x%10)+'0');
}
#define abs(x) (x>0?x:-x)
class frac{
private:
int z,m;
public:
frac(int x=0,int y=1){
z=x,m=y;
fixed();
}
frac fixed(){
int gcd=__gcd(abs(z),abs(m));
if(m<0){
m*=-1;z*=-1;
}
if(z==0){
m=1;return *this;
}
if(gcd==0) return *this;
z/=gcd;m/=gcd;
return *this;
}
frac upside(){
return frac(m,z);
}
frac operator = (pair<int,int>A){
z=A.first;m=A.second;fixed();
return *this;
}
frac operator + (frac A){
return (frac(z*A.m+m*A.z,m*A.m)).fixed();
}
frac operator * (frac A){
// cout<<"multi ";this->print();putchar(' ');
// A.print();putchar('=');
int gcd1=__gcd(z,A.m);
int gcd2=__gcd(A.z,m);
frac ans=(frac((z/gcd1)*(A.z/gcd2),(m/gcd2)*(A.m/gcd1))).fixed();
// ans.print();putchar('\n');
return ans;
}
frac operator / (frac A){
return (*this*A.upside()).fixed();
}
frac operator -(){
return frac(-z,m);
}
frac operator -(frac A){
return *this+(-A);
}
bool operator <(frac A){
return z*A.m<A.z*m;
}
bool operator ==(frac A){
return z*A.m==A.z*m;
}
bool operator >(frac A){
return !(*this==A and *this<A);
}
void print(){
fixed();
_print(z);putchar('/');_print(m);
// cout<<z<<"/"<<m<<endl;
}
frac _abs(){
return frac(abs(z),abs(m));
}
long double it(){
return z*1.0/m;
}
};
struct node{
signed x,y;
}p[1000001],s[1000001];
signed n;
double ans,mid;
double multi(node a1,node a2,node b1,node b2){
return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double dis(node p1,node p2){
return sqrt((double)(p2.y-p1.y)*(p2.y-p1.y)*1.0+(double)(p2.x-p1.x)*(p2.x-p1.x)*1.0);
}
bool cmp(node p1,node p2){
double tmp=multi(p[1],p1,p[1],p2);
if(tmp>0) return true;
if(tmp==0 and dis(p[0],p1)<dis(p[0],p2)) return true;
return false;
}
int sqr_vector_dis(node a){
return (__int128)a.x*a.x+(__int128)a.y*a.y;
}
int vector_multi(node a,node b){
return abs((__int128)a.x*b.x+(__int128)a.y*b.y);
}
void print_node(node a){
// cout<<"("<<a.x<<","<<a.y<<") ";
}
frac dist(node a,node b,node c){
// cout<<"dist ";print_node(a);print_node(b);print_node(c);putchar(' ');
//distance from c to line ab
node vector1={b.x-a.x,b.y-a.y};
node vector2={b.x-c.x,b.y-c.y};
// cout<<"::";print_node(vector1);print_node(vector2);
frac ans=
frac(vector_multi(vector1,vector2)*vector_multi(vector1,vector2)
,sqr_vector_dis(vector1)*sqr_vector_dis(vector2));
ans=-ans+1;ans=ans*sqr_vector_dis(vector2);ans=ans*frac(1,4);
// cout<<"= ";ans.print();putchar('\n');
return ans;
}
signed main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&p[i].x,&p[i].y);
if(i!=1 and p[i].y<p[1].y){
mid=p[1].y;p[1].y=p[i].y;p[i].y=mid;
mid=p[1].x;p[1].x=p[i].x;p[i].x=mid;
}
}
sort(p+2,p+1+n,cmp);
s[1]=p[1];
int tot=1;
for(int i=2;i<=n;i++){
while(tot>1 and multi(s[tot-1],s[tot],s[tot],p[i])<=0) tot--;
tot++;
s[tot]=p[i];
}
s[tot+1]=p[1];int now=1;
frac ans;
for(int i=1;i<=tot;i++){
//s[i] s[i+1]
while(dist(s[i],s[i+1],s[now]).it()<dist(s[i],s[i+1],s[(now==tot?1:now+1)]).it()){
now=(now==tot?1:now+1);
}
if(dist(s[i],s[i+1],s[now]).it()>ans.it()){
ans=dist(s[i],s[i+1],s[now]);
}
}
ans.print();
}
标签:fixed,return,int,破防,ans,operator,frac,一节课,圆锥曲线
From: https://www.cnblogs.com/HaneDaCafe/p/18427838